Climbers

Task

A mountain range can be represented as a broken line that starts and ends at sea level (altitude $0$) and has strictly positive altitudes in between (these are called inner altitudes). Alice and Bob start climbing the mountain range from both ends. They can move along the mountain range, back and forth, but they must stay at the same altitude (between them).

The effort of a path taken by Alice is the sum of absolute differences in altitudes on the path. Specifically, if Alice’s path begins at altitude $h_1 = 0$, changes directions at altitudes $h_2, h_3, \dots, h_{P-1}$ and ends at altitude $h_P$, then the effort of that path is $|h_2−h_1|+|h_3−h_2|+\dots+|h_P−h_{P−1}|$. (It follows that Bob will make an equal effort during this time).

Find the smallest effort Alice and Bob need to make in order to meet.

Input data

The mountain range is encoded as an array of $N$ integers containing the altitudes of the segment endpoints. The first line contains $N$. The second line contains the $N$ integers. The first and last integers are guaranteed to be $0$.

Output data

Print a single integer, the minimum effort required for Alice and Bob to meet. If there is no way for them to meet, print the word NO instead.

Constraints and clarifications

• $3 \leq N \leq 5 \ 000$
• Inner altitudes are between $1$ and $1 \ 000 \ 000$.
• Test cases will be scored individually.

Example 1

stdin

5
0 4 2 7 0

stdin

11

Explanation

Alice and Bob move towards one another to altitude $4$.

Then they both move right and descend to altitude $2$.

Finally, they move towards one another and meet at altitude $7$.

Example 2

stdin

7
0 10 1 20 5 10 0

stdin

48