Problem Description

A scheduling center is responsible for voltage scheduling for $N$ parallel power transmission cables in a city. These cables are numbered from $1$ to $N$ from left to right. Initially, the output voltage of all cables is $0$ kV.

To meet the electricity demand of different areas, cable $i$ must finally be stabilized at voltage $v_i$ kV. To achieve this, the scheduling center is equipped with an “interval voltage boosting device”: it can be activated once per day. Each time, an engineer may choose any continuous interval $[L, R]$ ($1 \leq L \leq R \leq N$), and increase the output voltage of all cables in this interval by $1$ kV at the same time.

Given the target voltage sequence $v_1, v_2, \cdots, v_N$, compute the minimum number of days needed to make the voltage of each cable reach exactly its corresponding target value.

Input Format

The first line contains an integer $N$, indicating the number of power transmission cables.

The second line contains $N$ integers $v_1, v_2, \cdots, v_N$, where $v_i$ indicates the target voltage (in kV) that the $i$-th cable needs to reach.

Output Format

Output one integer in one line, indicating the minimum number of days required to make the voltages of all cables reach exactly the target values.

4
1 2 1 2

3

Hint

Constraints

For $30\%$ of the testdata, $1 \leq N \leq 10^3$.

For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $0 \leq v_i \leq 10^9$.

Translated by ChatGPT 5