Sequence Reduction

Bob loves sequences. You are given a sequence of n non‐negative integers \(a_1, a_2, \cdots, a_n\). In each move, you can choose one of the following operations:

• Choose an interval \([l, r]\) and subtract 1 from every element in that interval.
• Choose an interval \([l, r]\) and subtract 1 from every element in that interval with odd index.
• Choose an interval \([l, r]\) and subtract 1 from every element in that interval with even index.

Your task is to determine the minimum number of moves required to reduce every element of the sequence to 0.

Note: The indices are 1-indexed. All formulas should be interpreted in \(\LaTeX\) format.

Observation and Hint:

One way to think about the problem is to first apply a number of full interval operations (which subtract from every element) and then handle the residual differences for the odd and even indexed elements separately. Define \(x\) as the number of full interval operations you perform. After these operations, each element becomes \(a_i - x\). For the remaining values on odd indices (and similarly for even indices), the minimal number of interval operations needed to reduce a 1D sequence \(b\) to 0 is given by:

[ f(b) = b_1 + \sum_{i=2}^{k} \max(0, b_i - b_{i-1}), ]

where \(b_1, b_2, \dots, b_k\) are the elements (in order) of the corresponding group (odd or even). Hence, if we let \(m = \min_{1 \le i \le n} a_i\), an optimal strategy is to choose \(x = m\) and then compute the cost for odd-indexed and even-indexed positions separately.

The final answer is given by:

[ \text{answer} = m + \Bigl[(a_1-m) + \sum_{\substack{i \ge 3\i \text{ odd}}} \max(0, a_i - a_{i-2})\Bigr] + \Bigl[\begin{array}{ll}\text{if } n \ge 2:& (a_2-m) + \sum_{\substack{i \ge 4\ i \text{ even}}} \max(0, a_i - a_{i-2})\ \text{else}:& 0 \end{array}\Bigr]. ]

Solve the problem by reading the value of n and the sequence, then computing the minimum number of moves accordingly.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), denoting the length of the sequence. The second line contains n non-negative integers \(a_1, a_2, \dots, a_n\) (0 ≤ a_i ≤ 10⁹), representing the sequence.

outputFormat

Output a single integer, the minimum number of moves required to reduce all elements of the sequence to 0.

sample

2
3 5

5