#include <bits/stdc++.h>
#define int long long
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n;
std::cin >> n;
std::vector<int> a(n);
std::vector<int> d(n - 1);
for (int i = 0; i < n; i++)
{
std::cin >> a[i];
}
for (int i = 0; i < n - 1; i++)
{
d[i] = (a[i + 1] - a[i]);
}
std::vector<int> pref(n - 1);
for (int i = 0; i < n - 1; i++)
{
if (i == 0)
{
if (d[i] <= 0)
{
pref[i] = std::abs(d[i]) + 1;
}
}
else
{
if (d[i] <= 0)
{
pref[i] = pref[i - 1] + std::abs(d[i]) + 1;
}
else
{
pref[i] = pref[i - 1];
}
}
}
std::vector<int> suf(n - 1);
for (int i = n - 2; i >= 0; i--)
{
if (i == n - 2)
{
if (d[i] >= 0)
{
suf[i] = d[i] + 1;
}
}
else
{
if (d[i] >= 0)
{
suf[i] = suf[i + 1] + d[i] + 1;
}
else
{
suf[i] = suf[i + 1];
}
}
}
int best = 1e15;
best = std::min(pref.back(), suf[0]);
for (int i = 1; i < n - 1; i++)
{
best = std::min(best, std::max(pref[i - 1], suf[i]));
}
std::cout << best;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |