#include<bits/stdc++.h>
using namespace std;
template < class S, class T> inline S max_L( S a,T b) {
return a>= b? a: b;
}
template < class S, class T> inline S chmin( S & a, T b) {
if ( a> b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
int movesToMakeZigzag( vector< int > & A) {
int N, i, j, res= 1073709056 , tmp;
N = A.size ( ) ;
tmp = 0 ;
for ( i= 0 ; i< N; i+ = 2 ) {
j = 1073709056 ;
if ( i- 1 >= 0 ) {
chmin( j, A[ i- 1 ] ) ;
}
if ( i+ 1 < N ) {
chmin( j, A[ i+ 1 ] ) ;
}
tmp + = max_L( 0 , A[ i] - j+ 1 ) ;
}
chmin( res, tmp) ;
tmp = 0 ;
for ( i= 1 ; i< N; i+ = 2 ) {
j = 1073709056 ;
if ( i- 1 >= 0 ) {
chmin( j, A[ i- 1 ] ) ;
}
if ( i+ 1 < N ) {
chmin( j, A[ i+ 1 ] ) ;
}
tmp + = max_L( 0 , A[ i] - j+ 1 ) ;
}
chmin( res, tmp) ;
return res;
}
}
;
// cLay varsion 20190810-2
// --- original code ---
// #define main dummy_main
//
// {
// }
//
// #undef main
//
// class Solution {
// public:
// int movesToMakeZigzag(vector<int>& A) {
// int i, j, N;
// int res = int_inf, tmp;
//
// N = A.size();
//
// tmp = 0;
// for(i=0;i<N;i+=2){
// j = int_inf;
// if(i-1 >= 0) j <?= A[i-1];
// if(i+1 < N ) j <?= A[i+1];
// tmp += max(0, A[i]-j+1);
// }
// res <?= tmp;
//
// tmp = 0;
// for(i=1;i<N;i+=2){
// j = int_inf;
// if(i-1 >= 0) j <?= A[i-1];
// if(i+1 < N ) j <?= A[i+1];
// tmp += max(0, A[i]-j+1);
// }
// res <?= tmp;
//
// return res;
// }
// };
//
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdGVtcGxhdGU8Y2xhc3MgUywgY2xhc3MgVD4gaW5saW5lIFMgbWF4X0woUyBhLFQgYil7CiAgcmV0dXJuIGE+PWI/YTpiOwp9CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIGNobWluKFMgJmEsIFQgYil7CiAgaWYoYT5iKXsKICAgIGE9YjsKICB9CiAgcmV0dXJuIGE7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgaW50IG1vdmVzVG9NYWtlWmlnemFnKHZlY3RvcjxpbnQ+JiBBKXsKICAgIGludCBOLCBpLCBqLCByZXM9MTA3MzcwOTA1NiwgdG1wOwogICAgTiA9IEEuc2l6ZSgpOwogICAgdG1wID0gMDsKICAgIGZvcihpPTA7aTxOO2krPTIpewogICAgICBqID0gMTA3MzcwOTA1NjsKICAgICAgaWYoaS0xID49IDApewogICAgICAgIGNobWluKGosIEFbaS0xXSk7CiAgICAgIH0KICAgICAgaWYoaSsxIDwgTiApewogICAgICAgIGNobWluKGosIEFbaSsxXSk7CiAgICAgIH0KICAgICAgdG1wICs9bWF4X0woMCwgQVtpXS1qKzEpOwogICAgfQogICAgY2htaW4ocmVzLCB0bXApOwogICAgdG1wID0gMDsKICAgIGZvcihpPTE7aTxOO2krPTIpewogICAgICBqID0gMTA3MzcwOTA1NjsKICAgICAgaWYoaS0xID49IDApewogICAgICAgIGNobWluKGosIEFbaS0xXSk7CiAgICAgIH0KICAgICAgaWYoaSsxIDwgTiApewogICAgICAgIGNobWluKGosIEFbaSsxXSk7CiAgICAgIH0KICAgICAgdG1wICs9bWF4X0woMCwgQVtpXS1qKzEpOwogICAgfQogICAgY2htaW4ocmVzLCB0bXApOwogICAgcmV0dXJuIHJlczsKICB9Cn0KOwovLyBjTGF5IHZhcnNpb24gMjAxOTA4MTAtMgoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIAovLyB7Ci8vIH0KLy8gCi8vICN1bmRlZiBtYWluCi8vIAovLyBjbGFzcyBTb2x1dGlvbiB7Ci8vIHB1YmxpYzoKLy8gICBpbnQgbW92ZXNUb01ha2VaaWd6YWcodmVjdG9yPGludD4mIEEpIHsKLy8gICAgIGludCBpLCBqLCBOOwovLyAgICAgaW50IHJlcyA9IGludF9pbmYsIHRtcDsKLy8gCi8vICAgICBOID0gQS5zaXplKCk7Ci8vIAovLyAgICAgdG1wID0gMDsKLy8gICAgIGZvcihpPTA7aTxOO2krPTIpewovLyAgICAgICBqID0gaW50X2luZjsKLy8gICAgICAgaWYoaS0xID49IDApIGogPD89IEFbaS0xXTsKLy8gICAgICAgaWYoaSsxIDwgTiApIGogPD89IEFbaSsxXTsKLy8gICAgICAgdG1wICs9IG1heCgwLCBBW2ldLWorMSk7Ci8vICAgICB9Ci8vICAgICByZXMgPD89IHRtcDsKLy8gCi8vICAgICB0bXAgPSAwOwovLyAgICAgZm9yKGk9MTtpPE47aSs9Mil7Ci8vICAgICAgIGogPSBpbnRfaW5mOwovLyAgICAgICBpZihpLTEgPj0gMCkgaiA8Pz0gQVtpLTFdOwovLyAgICAgICBpZihpKzEgPCBOICkgaiA8Pz0gQVtpKzFdOwovLyAgICAgICB0bXAgKz0gbWF4KDAsIEFbaV0taisxKTsKLy8gICAgIH0KLy8gICAgIHJlcyA8Pz0gdG1wOwovLyAKLy8gICAgIHJldHVybiByZXM7Ci8vICAgfQovLyB9OwovLyAK