Climbers

Time limit0.8sMemory limit1024 MB

Summary

Given a mountain range as altitudes that start and end at 0, find the minimum total effort Alice and Bob need to meet at the same altitude.

Level: Medium7 of 10
Topics: Array, Brute force, Dynamic programming
Solved: No attempts yet

Problem

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 in-between altitudes are called inner altitudes. Alice and Bob start climbing from both ends. They can move along the range, back and forth, but they must stay at the same altitude as each other.

The effort of a path taken by Alice is the sum of absolute differences in altitudes along the path. If Alice's path begins at altitude $h_1 = 0$ , changes direction at altitudes $h_2, h_3, \ldots, h_{P-1}$ , and ends at altitude $h_P$ , then the effort is $|h_2-h_1|+|h_3-h_2|+\cdots+|h_P-h_{P-1}|$ . Bob makes an equal effort during the same time.

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

Input

The mountain range is given as an array of $N$ integers, the altitudes of the segment endpoints. The first line contains $N$ . The second line contains the $N$ integers. The first and last integers are always 0.

Output

Print a single integer, the minimum effort required for Alice and Bob to meet. If they cannot meet, print NO.

Constraints

$3 \le N \le 5{,}000$

Inner altitudes are between 1 and 1,000,000.

Examples2

Example 1
Input
```
5
0 4 2 7 0
```
Expected output
```
11
```
Example 2
Input
```
7
0 10 1 20 5 10 0
```
Expected output
```
48
```