Chunchun is a road engineer responsible for paving a road of length $n$.

The main task in paving the road is to fill in the sunken ground. The road can be viewed as $n$ connected segments, and initially, the depth of the sunken ground in the $i$-th segment is $d_i$.

Every day, Chunchun can choose a continuous interval $[L, R]$ and fill in every segment within this interval, reducing their sunken depth by $1$. When choosing an interval, it must be guaranteed that the sunken depth of every segment within the interval is not $0$ before filling.

Chunchun hopes you can help him design a plan to make the sunken depth of all segments on the road $0$ in the shortest possible time.

Input

The first line contains a single integer $n$, representing the length of the road. The second line contains $n$ integers, separated by spaces, where the $i$-th integer is $d_i$.

Output

The output contains only one integer, which is the minimum number of days required to complete the task.

Examples

Input 1

6
4 3 2 5 3 5

Output 1

9

Note

One feasible optimal plan is to choose, in order: $[1,6], [1,6], [1,2], [1,1], [4,6], [4,4], [4,4], [6,6], [6,6]$.

Input 2

(See the files road/road2.in in the problem directory)

Output 2

(See the files road/road2.ans in the problem directory)

Constraints

For $30\%$ of the data, $1 \le n \le 10$; For $70\%$ of the data, $1 \le n \le 1000$; For $100\%$ of the data, $1 \le n \le 100000$, $0 \le d_i \le 10000$.