Cho một dãy núi có thể được biểu thị dưới dạng một đường đứt đoạn bắt đầu và kết thúc ở mực nước biển (độ cao 0) và có các độ cao dương ở giữa.

Alice và Bob bắt đầu leo lên dãy núi từ hai đầu. Họ có thể di chuyển dọc theo dãy núi, đi thẳng hoặc lùi lại, nhưng họ phải ở cùng một độ cao. Công sức di chuyển trên một con đường do Alice thực hiện là tổng của sự phân biệt về độ cao trên đường đi. Cụ thể, nếu đường đi của Alice bắt đầu ở độ cao \(h_1=0\), và đổi hướng ở độ cao \(h_2,h_3,...,h_{P-1}\) và kết thúc ở độ cao \(h_P\), thì công sức di chuyển trên con đường đó là \(|h_2-h_1 |+|h_3-h_2 |+...+|h_P-h_(P-1) | \). Công sức của Bob bỏ ra là bình đẳng với Alice trong thời gian này.

Yêu cầu:

• Tìm công sức nhỏ nhất mà Alice và Bob cần thực hiện để gặp nhau.

Input

• Dòng đầu tiên chứa \(N (3≤N≤5000)\)

• Dòng thứ hai chứa \(N\) số \(H_i\) là độ cao mô tả dãy núi \((0≤H_i≤10^6,H_1=H_N=0).\)

Output

• Đưa ra kết quả bài toán. Hoặc in ra 'NO' nếu không thể.

Ràng buộc

• Subtask 1 (30%): \(H_i\) phân biệt

• Subtask 2 (30%): \(N×max(Hi)≤4⋅10^4\)

• Subtask 3 (40%): không có ràng buộc gì thêm.

Sample Input

6
1 1 2 2 4 8
2 2 3 5 2 2

Sample Output

3