Optimize Context Switching

You may only increase array elements, and each increment is an integer in 0..10^18. An interior point counts as a peak only if it is strictly greater than both neighbors; endpoints do not count. First maximize the number of peaks, then minimize the total increase.

输入格式

The first line contains n, and the second line contains n initial values. The original gives no bounds on n or the initial values; this site uses 1≤n≤200000 with initial values in −10^9..10^9, and keeps the original upper limit of 10^18 per increment.

输出格式

Output a single integer answer.

样例 1

输入：

3
1 1 1

输出：

1

样例 2

输入：

5
5 1 1 1 5

输出：

10

样例 3

输入：

2
1 2

输出：

0

样例说明

The outputs of the three public examples are, in order: 1; 10; 0. Checked by independent enumeration or direct simulation.