시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.8 초 1024 MB73250.000%

문제

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 h1 = 0, changes directions at altitudes h2, h3, ..., hP-1 and ends at altitude hP, then the effort of that path is |h2−h1|+|h3−h2|+⋯+|hP−hP−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.

입력

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.

출력

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.

제한

  • 3 ≤ N ≤ 5,000
  • Inner altitudes are between 1 and 1,000,000.

서브태스크

번호배점제한
125

All inner altitudes are distinct.

225

N × H ≤ 40,000, where H is the highest altitude.

350

none

예제 입력 1

5
0 4 2 7 0

예제 출력 1

11

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.

예제 입력 2

7
0 10 1 20 5 10 0

예제 출력 2

48

채점 및 기타 정보

  • 예제는 채점하지 않는다.