#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, a[310000];
ll pre[310000] = {0}, suf[310000] = {0};
int main () {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
a[0] = a[n + 1] = -1;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1];
if (a[i] <= a[i - 1]) pre[i] += a[i - 1] + 1 - a[i];
}
for (int i = n; i >= 1; i--) {
suf[i] = suf[i + 1];
if (a[i] <= a[i + 1]) suf[i] += a[i + 1] + 1 - a[i];
}
ll ans = min(pre[n], suf[1]);
for (int i = 1; i <= n; i++) {
ll zz = max(suf[i + 1], a[i - 1] + 1LL - a[i]) + max(pre[i - 1], a[i + 1] + 1LL - a[i]);
ans = min(ans, zz);
}
cout << ans << '\n';
return 0;}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
504 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
504 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |