Định nghĩa trọng số của một nhóm số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong nhóm đó. (Nhóm có thể có 1 phần tử)

Ví dụ trọng số của nhóm \((3,1,7,2)\) là \(6\), trọng số của nhóm \((40,40)\) là \(0\), trọng số của nhóm \((1208)\) là \(0\).

Cho 1 dãy gồm \(n\) phần tử, phần tử thứ \(i\) có giá trị là \(a_i\).

Yêu cầu:

• Mỗi nhóm là 1 dãy các số liên tiếp.
• Giá trị của dãy số bằng tổng trọng số của tất cả các nhóm. Hãy tìm cách chia sao cho tổng trọng số đạt giá trị lớn nhất.

Input

• Dòng 1: chứa số nguyên \(n (1 \le n \le 10^5)\)
• Dòng 2: chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (-10^9 \le a_i \le 10^9)\)

Output

• Ghi ra giá trị lớn nhất của dãy.

Example

6
1 9 6 7 1 6

14