This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, a[200005];
long long pref[200005], suff[200005], sol;
int main()
{
int i;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
pref[1] = 0;
for (i = 2; i <= n; i++)
if (a[i] <= a[i - 1])
pref[i] = pref[i - 1] + a[i - 1] - a[i] + 1;
else
pref[i] = pref[i - 1];
suff[n] = 0;
for (i = n - 1; i >= 1; i--)
if (a[i] <= a[i + 1])
suff[i] = suff[i + 1] + a[i + 1] - a[i] + 1;
else
suff[i] = suff[i + 1];
sol = max(suff[1], pref[1]);
for (i = 2; i <= n; i++)
sol = min(sol, max(pref[i] , suff[i]));
cout << sol;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |