Posted by yjjr's blog on February 6, 2018

Polycarpplans to conduct a load testing of its new project Fakebook. He already agreedwith his friends that at certain points in time they will send requests toFakebook. The load testing will last n minutesand in the i-th minute friendswill send ai requests.

Polycarpplans to test Fakebook under a special kind of load. In case the informationabout Fakebook gets into the mass media, Polycarp hopes for a monotone increaseof the load, followed by a monotone decrease of the interest to the service.Polycarp wants to test this form of load.

Your taskis to determine how many requests Polycarp must add so that before some momentthe load on the server strictly increases and after that moment strictlydecreases. Both the increasing part and the decreasing part can be empty (i. e.absent). The decrease should immediately follow the increase. In particular,the load with two equal neigbouring values is unacceptable.

Forexample, if the load is described with one of the arrays [1, 2, 8, 4, 3], [1, 3, 5] or [10], then such load satisfies Polycarp (in eachof the cases there is an increasing part, immediately followed with adecreasing part). If the load is described with one of the arrays [1, 2, 2, 1], [2, 1, 2] or [10, 10], then such load does not satisfyPolycarp.

HelpPolycarp to make the minimum number of additional requests, so that theresulting load satisfies Polycarp. He can make any number of additionalrequests at any minute from 1 to n.

Input

The firstline contains a single integer n (1 ≤ n ≤ 100 000) — the duration ofthe load testing.

The secondline contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the number ofrequests from friends in the i-th minuteof the load testing.

Output

Print theminimum number of additional requests from Polycarp that would make the loadstrictly increasing in the beginning and then strictly decreasing afterwards.

Example

Input

5
1 4 3 2 5

Output

6

Input

5
1 2 2 2 1

Output

1

Input

7
10 20 40 50 70 90 30

Output

0

Note

In thefirst example Polycarp must make two additional requests in the third minuteand four additional requests in the fourth minute. So the resulting load willlook like: [1, 4, 5, 6, 5]. Intotal, Polycarp will make 6 additionalrequests.

In thesecond example it is enough to make one additional request in the third minute,so the answer is 1.

In thethird example the load already satisfies all conditions described in thestatement, so the answer is 0.

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

long long n,a[1000005],f[1000005],g[1000005],b[1000005],ans=1e18,s=0;
int main()
{
scanf("%d",&n);
rep(i,1,n){scanf("%d",&a[i]);b[i]=a[i];}
rep(i,1,n)
if(a[i]<=a[i-1]){f[i]=f[i-1]+a[i-1]+1-a[i];a[i]=a[i-1]+1;}else f[i]=f[i-1];
dep(i,n,1)
if(b[i]<=b[i+1]){g[i]=g[i+1]+b[i+1]+1-b[i];b[i]=b[i+1]+1;}else g[i]=g[i+1];
rep(k,0,n){
s=f[k]+g[k+1];
if(a[k]==b[k+1])s++;
if(s<ans)ans=s;
}
cout<<ans<<endl;
return 0;
}