Block Tower Construction

Spring Spring Kindergarten organizes its annual "Building Blocks Contest". This year, the contest is to build a tower with a width of \(n\) where the tower is composed of \(n\) blocks, each of width 1. The target height for the \(i\)-th block is given as \(h_i\).

Initially, there are no blocks built, which can be considered as \(n\) blocks of height 0. In each operation, you are allowed to select a contiguous segment \([l, r]\) (i.e. blocks from index \(l\) to \(r\), both inclusive) and increase the height of all blocks in that segment by 1.

Your task is to help the clever little M determine the minimum number of operations required to achieve the target heights.

Hint: An optimal strategy is to perform operations based on the differences between consecutive block heights. The answer can be computed by the formula:

[ \text{Answer} = h_1 + \sum_{i = 2}^{n} \max(0, h_i - h_{i-1}) ]

inputFormat

The first line contains a single integer \(n\) (1 \(\leq\) n \(\leq\) 10⁵), the number of blocks.

The second line contains \(n\) space-separated integers \(h_1, h_2, \dots, h_n\) (0 \(\leq\) h_i \(\leq\) 10⁹), the desired final heights of the blocks.

outputFormat

Output a single integer, the minimum number of operations required to build the tower as described.

sample

3
1 2 3

3