给定一个长度为
n
n
n的序列
{
a
n
}
\{a_n\}
{an},对于每个
i
∈
[
1
,
n
]
i \in [1,n]
i∈[1,n],求出一个最小的非负整数
p
p
p,是的
∀
j
∈
[
1
,
n
]
\forall j \in [1,n]
∀j∈[1,n],都有
a
j
≤
a
i
+
p
−
∣
i
−
j
∣
a_j \le a_i+p-\sqrt{|i-j|}
aj≤ai+p−∣i−j∣
1
≤
n
≤
5
e
5
,
0
≤
a
i
≤
1
e
9
1 \le n \le 5e5, 0 \le a_i \le 1e9
1≤n≤5e5,0≤ai≤1e9
//因为本题的转移代价是sqrt(i-j)而该函数的增长速度是逐渐下降的,
//所以可能存在某个j2>j1,在到某个i之后a[j2]+sqrt(i-j2) > a[j1]+sqrt(i-j1)(原本是小于的)
#include <bits/stdc++.h>
#define ft first
#define sd second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 5e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
int n, a[maxn], ans[maxn];
int q[maxn], k[maxn];
int find(int x, int y) {
int lc = y, rc = n, mc, res = n + 1;
while (lc <= rc) {
mc = (lc + rc) >> 1;
if (a[x] + sqrt(mc - x) <= a[y] + sqrt(mc - y))
res = mc, rc = mc - 1;
else
lc = mc + 1;
}
return res;
}
//k[i]放的是队列中第i个点与队列中的第i+1个点,什么时候第i个点的函数曲线会被第i+1个点超过
//队列中的k是单调递增的,如果存在一个i<i+1,但k(i)>k(i+1),意思就是函数曲线第i个点被i+1超过时,i+2早就超过了i+1,则i+1是无用的点
void solve() {
for (int i = 1, h = 1, t = 0; i <= n; i++) {
while (h < t && k[t - 1] > find(q[t], i))//保证单调递增,及判断t-1被t超过时,t不能被i超过
t--;
k[t] = find(q[t], i); //利用二分查找来得到k
q[++t] = i;
while (h < t && k[h] <= i) h++; //队头的k此时已经小过i了,所以弹出
ans[i] = max(ans[i], (int)(-a[i] + a[q[h]] + ceil(sqrt(i - q[h]))));
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
solve();
for (int i = 1; i <= n / 2; i++)
swap(a[i], a[n - i + 1]), swap(ans[i], ans[n - i + 1]);
solve();
for (int i = n; i >= 1; i--)
cout << ans[i] << endl;
}