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