1：TLE

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int s[200005], pm[200005];
int p[200005];
bool check(int k) {
	memset(pm, 0, sizeof(pm));
	int m = 2 * k - 1;
	for (int i = 1; i <= k; ++i) {
		p[i] = i;
	}
	for (int i = k + 1; i <= m; ++i) {
		p[i] = m - i + 1;
	}
	int j = 0;
	for(int i = 2; i <= m; ++i) {
		while(j > 0 && p[i] < p[j + 1]) {
			j = pm[j];
		}
		if(p[i] >= p[j + 1]) {
			++ j;
		}
		pm[i] = j;
	}
	j = 0;
	for(int i = 1; i <= n; ++i) {
		while (j > 0 && s[i] < p[j + 1]) {
			j = pm[j];
		}
		if (s[i] >= p[j + 1]) {
			++j;
		}
		if (j == m) {
			return 1;
//            printf("%d\n", i - m + 1);
//            j = pm[j];
		}
	}
	return 0;
}
signed main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	int l = 1, r = n, res = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) {
			l = mid + 1;
			res = mid;
		} else {
			r = mid - 1;
		}
	}
	cout << res;
	return 0;
}

2:AC

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n;
int s[N];
int p[N], pm[N];
bool check(int k) {
	memset(pm, 0, sizeof(pm));
	int m = 2 * k - 1;
	for (int i = 1; i <= k; ++i) {
		p[i] = i;
	}
	for (int i = k + 1; i <= m; ++i) {
		p[i] = m - i + 1;
	}
	int j = 0;
	for(int i = 2; i <= m; ++i) {
		while(j > 0 && p[i] < p[j + 1]) {
			j = pm[j];
		}
		if(p[i] >= p[j + 1]) {
			++ j;
		}
		pm[i] = j;
	}
	j = 0;
	for(int i = 1; i <= n; ++i) {
		while (j > 0 && s[i] < p[j + 1]) {
			j = pm[j];
		}
		if (s[i] >= p[j + 1]) {
			++j;
		}
		if (j == m) {
			return 1;
//            printf("%d\n", i - m + 1);
//            j = pm[j];
		}
	}
	return 0;
}
signed main() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	int l = 1, r = n, res = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) {
			l = mid + 1;
			res = mid;
		} else {
			r = mid - 1;
		}
	}
	cout << res;
	return 0;
}