coder force 2017-2018 ACM-ICPC, NEERC H. Load Testing (思維題)

H. Load Testing time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Polycarp plans to conduct a load testing of its new project Fakebook. He already agreed with his friends that at certain points in time they will send requests to Fakebook. The load testing will last n minutes and in the i-th minute friends will send ai requests.

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

Your task is to determine how many requests Polycarp must add so that before some moment the load on the server strictly increases and after that moment strictly decreases. 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.

For example, 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 each of the cases there is an increasing part, immediately followed with a decreasing 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 satisfy Polycarp.

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

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the duration of the load testing.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the number of requests from friends in the i-th minute of the load testing.

Output

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

Examples Input Copy

5
1 4 3 2 5
      

Output

6
      

Input Copy

5
1 2 2 2 1
      

Output

1
      

Input Copy

7
10 20 40 50 70 90 30
      

Output

Note

In the first example Polycarp must make two additional requests in the third minute and four additional requests in the fourth minute. So the resulting load will look like: [1, 4, 5, 6, 5]. In total, Polycarp will make 6 additional requests.

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

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

題意:

給你一個序列，問你如何通過增加其中的幾個數，使得這個序列先上升後下降，或這一直上升，或者一直下降,求如何增加，使得增加部分最小

解析：

大佬的思路，先正着掃一遍，求使得正着遞增的話，各個數所需要增加的值，再逆着掃一遍，求使得逆着掃一遍的話，各個數增加的值。

再将正着的遞增值求字首和，逆着的遞增值求字尾和。

最後掃一遍，求如果将i作為趨勢改變的點，整個序列所需增加的值，sum1[i]+sum2[i]-min(sum1[i]-sum1[i-1],sum2[i]-sum2[i+1]);

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f

const int MAX = 1e5 + 100;
typedef long long int lli;

int n;

lli a[MAX];
lli sum1[MAX];
lli sum2[MAX];


int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	sum1[1]=0;
	lli num=a[1];
	for(int i=2;i<=n;i++)
	{
		num=max(num+1,a[i]);
		sum1[i]+=num-a[i]+sum1[i-1];
	}
	num=a[n];
	for(int i=n-1;i>=1;i--)
	{
		num=max(num+1,a[i]);
		sum2[i]+=num-a[i]+sum2[i+1];
	}

	lli minn=INF;
	int minnum=-1;
	for(int i=1;i<=n;i++)
	{
		lli tmp=sum1[i]+sum2[i]-min(sum1[i]-sum1[i-1],sum2[i]-sum2[i+1]);
		if(minn>tmp)
		{
			minn=tmp;
		}
	}
	printf("%lld\n",minn);
	return 0;
}