410793: GYM104114 I Inadequate Operation

You are given an array $$$a$$$ of $$$n$$$ nonnegative integers. In one operation, you can choose any $$$i$$$ such that $$$1\le i \le n-1$$$ and $$$\max(a_i, a_{i+1})>0$$$, and replace both $$$a_i$$$ and $$$a_{i+1}$$$ by $$$\max(a_i, a_{i+1}) - 1$$$.

Find the smallest number of operations required to make all elements equal to $$$0$$$. It can be proven that it's always possible to make all numbers equal to $$$0$$$.

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 200\:000$$$) — the number of integers.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)  — the elements of the array.

Output a single integer — the smallest number of operations required to make all elements equal to $$$0$$$.

3
2 0 22

24

3
0 2022 0

2022

6
30 20 10 10 20 30

70

In the first test case, you can apply this operation $$$2$$$ times to $$$i = 1$$$, and then $$$22$$$ times to $$$i = 2$$$.

In the second test case, you can apply this operation $$$2022$$$ times to $$$i = 1$$$.