#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops") //main
//#pragma GCC target("avx2") //cf...
//#pragma GCC target("sse4") //Quera
#define ll long long
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;
#define f first
#define s second
#define lc 2*id
#define rc 2*id+1
#define all(x) x.begin(),x.end()
#define pb push_back
#define pp pop_back
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())
string pr(int* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr( ll* vv,int l,int r){for(int i=l;i<r;i++)cout<<vv[i]<<" ";return "";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr( vector<ll> vv){for(auto i:vv)cout<<i<<" ";return "";}
string pr(pii* vv,int l,int r){for(int i=l;i<r;i++)cout<<"( "<<vv[i].f<<","<<vv[i].s<<" ) ";return "";}
string pr(vector<pii> vv){for(auto i:vv)cout<<"( "<<i.f<<","<<i.s<<" ) ";return "";}
const int L = 2e5+10,mod = 1e9+7;
const ll inf = 1000ll*1000*1000*1000*1000*1000+10;
int n;
ll a[L],ps[L],sf[L];
int main(){
//ofstream cout ("out.out");
//ifstream cin ("in.in");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
ps[i] = ps[i-1] + max(a[i-1]-a[i]+1,0ll);
}
for(int i=n-1;i>=1;i--){
sf[i] = sf[i+1] + max(a[i+1]-a[i]+1,0ll);
}
ll ans = inf;
for(int i=1;i<=n;i++){
ans = min(ans,max(ps[i],sf[i]));
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |