Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Một đoạn con liên tiếp của dãy ~A~ là đoạn ~a_l, a_{l+1}, ..., a_r~ với ~1 \le l \le r \le n~, giá trị đoạn con là độ chênh lệch của giá trị lớn nhất và giá trị nhỏ nhất của đoạn con. Giá trị của dãy số là tổng giá trị tất cả các đoạn con liên tiếp của dãy. Ví dụ: Cho dãy số 2 4 1 ta có các đoạn con liên tiếp ~\{2\}, \{4\}, \{1\}, \{2, 4\}, \{4, 1\}, \{2, 4, 1\}~, giá trị dãy số là ~0 + 0 + 0 + (4-2) + (4-1) + (4-1) = 0 + 0 + 0 + 2 + 3 + 3 = 8~.

Yêu cầu: Với dãy số nguyên dương ~a_1, a_2, ..., a_n~ có ~n~ phần tử, hãy tính giá trị của dãy số.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^7~). Các số trong tệp cách nhau bởi dấu cách.

Output

Một số nguyên duy nhất là giá trị của dãy số.

Sample Input

3
2 4 1

Sample Output

8

Subtasks