The Chun-Chun Kindergarten is holding its annual "Building Block Competition." This year's competition involves building a skyscraper of width $n$. The skyscraper can be viewed as being composed of $n$ blocks, each of width 1, where the final height of the $i$-th block needs to be $h_i$.

Before building begins, there are no blocks (which can be viewed as $n$ blocks of height 0). In each subsequent operation, the children can choose a continuous interval $[L, R]$ and increase the height of all blocks from the $L$-th to the $R$-th (inclusive) by 1.

Xiao M is a clever child who quickly figured out the optimal strategy to build the skyscraper with the minimum number of operations. However, she is not a child who likes to do manual labor, so she asks you to implement this strategy and find the minimum number of operations required.

Input

The input consists of two lines. The first line contains a single integer $n$, representing the width of the skyscraper. The second line contains $n$ integers, where the $i$-th integer is $h_i$.

Output

Output a single line containing the minimum number of operations required to build the skyscraper.

Examples

Input 1

5
2 3 4 1 2

Output 1

5

Note

One possible optimal strategy is to choose the following intervals in sequence: $[1, 5], [1, 3], [2, 3], [3, 3], [5, 5]$

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 h_i \le 10000$.