#include #include #include using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin>>n; vector a(n); for(int i = 0;i>a[i]; ll ans = 1e18; vector>> dp(n,vector>(n,vector(2,1e18))); dp[0][n-1][0] = -1; for(int i = n;i>0;i--){ for(int j = 0;j=n) continue; for(int t = 0;t<2;t++){ int p; if(t==0) p = le - 1; else p = ri + 1; for(int nt = 0;nt<2;nt++){ int np; if(nt==0) np = le; else np = ri; ll ti = dp[le][ri][t]; ti += abs(p-np); if(nt==0) ti = max(ti,a[le]); else ti = max(ti,a[ri]); if(nt==0){ if(ri==le){ ans = min(ans,ti); }else{ dp[le+1][ri][nt] = min(dp[le+1][ri][nt],ti); } }else{ if(ri==le){ ans = min(ans,ti); }else{ dp[le][ri-1][nt] = min(dp[le][ri-1][nt],ti); } } } } } } cout<