Panoramic Photography Gym - 101149J（挺有意思的一个思维题）

Most of the students of the law school prefer visiting photo club to the competitions in Roman law. Members of the photo club visit different interesting places, take photos of each other in front of them, and then rate their photos.

Once they appeared on a unbelievably long street which had n buildings in a row. Every member of the photo club took a photo contained, besides the members of the club and people passing by, a segment of the street. In other words, if you number the buildings in the order they are located on the street, each photo contained some buildings with the consecutive numbers.

Some day a Roman law professor of that law school came across the exhibition of the photos from that street. He hasn't remembered how many photos were there, but he has noticed that the i-th building was captured on ai photos. Now he wants to estimate the minimal number of his students in the photo club, considering that no one could present more that one photo at the exhibition.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of buildings.

The second line contains n space-separated integers: ai (0 ≤ ai ≤ 109) — the number of photos that contain the i-th building.

Output

Output a single integer — the minimal number of students in the photo club.

Examples

Input

4
1 3 2 0

Output

3

Input

6
1 2 3 1 2 3

Output

5

题目意思：n个数初始值都为0，每次可以在连续的区间上增加1，问最少操作次数使得最终到达a[1], a[2], a[3].....a[n]的状态。

solution：如果a[i] > a[i - 1]的话，那么在a[i - 1]刚好被覆盖的时候它还没有被覆盖，那么需要a[i] - a[i - 1]次操作来达到满状态。每一个连续区间都是这种情况，只要a[i] < a[i - 1]那么就是下一个连续区间了。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 2 * 1e5 + 100;

int a[maxn];
int n;

int main()
{
	//freopen("in.txt", "r", stdin);
	cin >> n;
	for(int i = 1; i <= n; ++ i)
	{
		scanf("%d", &a[i]);
	}
	long long ans = a[1];
	for(int i = 2; i <= n; ++ i)
	{
		if(a[i] > a[i - 1])
			ans += a[i] - a[i - 1];
	}
cout << ans << endl;
	return 0;
}