410793: GYM104114 I Inadequate Operation
Description
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$$$.
InputThe 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.
OutputOutput a single integer — the smallest number of operations required to make all elements equal to $$$0$$$.
ExamplesInput3 2 0 22Output
24Input
3 0 2022 0Output
2022Input
6 30 20 10 10 20 30Output
70Note
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$$$.