Artifact 3c712bb16a6c8631c6da6c5ef8c17e64de41ec5e
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class ConvexSequence { public:
long long getMinimum(vector <int> a)
{
int i = min_element(a.begin(), a.end()) - a.begin();
vector<LL> pre(a.begin(), a.begin()+i+1);
reverse(pre.begin(), pre.end());
vector<LL> post(a.begin()+i, a.end());
return convex_incr(pre) + convex_incr(post);
}
LL convex_incr(vector<LL> a)
{
if( a.empty() )
return 0;
for(int i=a.size()-1; i>=0; --i)
a[i] -= a[0];
LL cnt = 0;
for(int i=1; i<a.size()-1; ++i)
{
LL amax = a[i];
for(int k=i+1; k<a.size(); ++k)
amax = min(amax, (a[k] - a[i-1]) / (k-(i-1)) + a[i-1]);
if( amax < a[i] ) {
cnt += a[i]-amax;
a[i] = amax;
}
}
return cnt;
}
};