1 /************************************************************** 2     Problem: 2216 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:4128 ms 7     Memory:16432 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 typedef double lf;16 const int N = 500005;17  18 struct data {19     int l, r, p;20     data() {}21     data(int _l, int _r, int _p) : l(_l), r(_r), p(_p) {}22 }q[N];23  24 int n, a[N];25 lf f[N], g[N];26  27 inline int read() {28     int x = 0, sgn = 1;29     char ch = getchar();30     while (ch < ‘0‘ || ‘9‘ < ch) {31         if (ch == ‘-‘) sgn = -1;32         ch = getchar();33     }34     while (‘0‘ <= ch && ch <= ‘9‘) {35         x = x * 10 + ch - ‘0‘;36         ch = getchar();37     }38     return sgn * x;39 }40  41 inline lf calc(int j, int i) {42     return a[j] - a[i] + sqrt(abs(i - j));43 }44  45 int find(data t, int x) {46     int l = t.l, r = t.r, mid;47     while (l <= r) { 48         mid = l + r >> 1;49         if (calc(t.p, mid) > calc(x, mid))50             l = mid + 1;51         else r = mid - 1;52     }53     return l;54 }55  56 void dp(lf *F) {57     for (int i = 1, h = 1, t = 0, tmp; i <= n; ++i) {58         ++q[h].l;59         if (h <= t && q[h].r < q[h].l) ++h;60         if (h > t || calc(i, n) > calc(q[t].p, n)) {61             while (h <= t && calc(q[t].p, q[t].l) < calc(i, q[t].l))62                 --t;63             if (h > t) q[++t] = data(i, n, i);64             else {65                 tmp = find(q[t], i);66                 q[t].r = tmp - 1;67                 q[++t] = data(tmp, n, i);68             }69         }70         F[i] = calc(q[h].p, i);71     }72 }73  74 int main() {75     int i;76     n = read();77     for (i = 1; i <= n; ++i)78         a[i] = read();79     dp(f);80     reverse(a + 1, a + n + 1);81     dp(g);82     for (i = 1; i <= n; ++i)83         printf("%d\n", (int) ceil(max(f[i], g[n - i + 1])));84     return 0;85 }86