如题，本地对拍暂时还没有拍出来，觉得写的也挺对的（雾，求各位巨佬帮帮忙看看 qwq

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6;
int a[N + 10], st[N + 10];
int sqt(int x) {
	int L = 0, R = 2000, ans = 0;
	while(L <= R) {
		int mid = (L + R) >> 1;
		if(mid * mid >= x) ans = mid, R = mid - 1;
		else L = mid + 1;
	}
	return ans;
}
int Abs(int x) {
	return max(x, -x);
}
int opt[N + 10], ans1[N + 10], ans2[N + 10];
int calc(int i, int j) {
	return a[j] - a[i] + st[Abs(j - i)];
}
void dp(int l, int r, int kl, int kr) {
	int mid = (l + r) >> 1;

	opt[mid] = kl;
	for(int j = kl + 1; j <= min(kr, mid); j++)
		if(calc(mid, j) > calc(mid, opt[mid]))
			opt[mid] = j;

	if(l < mid) dp(l, mid - 1, kl, opt[mid]);
	if(r > mid) dp(mid + 1, r, opt[mid], kr);
}
signed main() {
	int n; cin >> n;
	st[0] = 0;
	for(int i = 1; i <= n; i++) 
		cin >> a[i], st[i] = sqt(i);

	dp(1, n, 1, n);
	for(int i = 1; i <= n; i++)
		ans1[i] = max(ans1[i], calc(i, opt[i]));

	reverse(a + 1, a + n + 1);
	dp(1, n, 1, n);
	for(int i = 1; i <= n; i++)
		ans2[n - i + 1] = max(ans2[n - i + 1], calc(i, opt[i]));
	for(int i = 1; i <= n; i++)
		cout << max(ans1[i], ans2[i]) << endl;
}