Theme portal
Decision-making monotonicity optimization qwq
The monotonicity of decision is the current state I I i, two decision j, K (j & lt; k) j, K (j & lt; k) j, K (j < k). if K is better, then J will never reverse when I increases
This is the time to satisfy the monotony of decision-making
Then it is obtained that each decision corresponds to an interval so that the decision is the optimal solution for the state in the interval.

Let's talk about this topic.
A bit of a mystery.
fi=max(aj+∣j−i∣)f_i=max(a_j+\sqrt{|j-i|})fi​=max(aj​+∣j−i∣​)
The way to get rid of absolute value is to do it over and over again.
Open a monotone queue with triples {l,r,pl,r,pl,r,p} to represent the corresponding interval [l,r][l,r][l,r]
Some properties and practices can be obtained.

• All the intervals put together are [1,n][1,n][1,n]
• iii enumerates + + q[h].l once per enumeration, and deletes if the corresponding interval of the team leader is empty
• For each state iii, the optimal decision is the head of the team
• The condition for adding i-decision at the end of the team is that decision I is better for state n than for decision-making end-to-state n.
• Then the corresponding interval is updated by dichotomy search critical value

Code:

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
struct data{
	int l, r, p;
}q[maxn];
int n, a[maxn];
double f[maxn], g[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

double calc(int j, int i){ return a[j] - a[i] + sqrt(abs(i - j)); }

int find(data t, int x){
	int l = t.l, r = t.r;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (calc(t.p, mid) > calc(x, mid)) l = mid + 1; else r = mid - 1;
	}
	return l;
}

void Dp(double *dp){
	int h = 1, t = 0;
	for (int i = 1; i <= n; ++i){
		if (h <= t && ++q[h].l > q[h].r) ++h;
		if (h > t || calc(q[t].p, n) < calc(i, n)){
			while (h <= t && calc(q[t].p, q[t].l) < calc(i, q[t].l)) --t;
			if (h > t) q[++t] = (data){i, n, i}; else{
				int tmp = find(q[t], i);
				q[t].r = tmp - 1;
				q[++t] = (data){tmp, n, i};
			}	
		}
		dp[i] = calc(q[h].p, i);
	}
}

int main(){
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	Dp(f);
	reverse(a + 1, a + 1 + n);
	Dp(g);
	for (int i = 1; i <= n; ++i) printf("%d\n", max(0, (int)ceil(max(f[i], g[n + 1 - i]))));
	return 0;
}