Cho dãy số nguyên \(a_1, a_2, \ldots, a_n\), tính \(\sum_{1\le l\le r\le n}( \max(a_l, a_{l + 1}, \ldots, a_{r}) - \min(a_l, a_{l + 1}, \ldots, a_{r}))\).

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n \le 2\cdot 10^5)\).
• Dòng thứ hai chứa \(n\) số \(a_1, a_2, \ldots, a_n\) \((1\le a_i\le n)\).

Output

• Ghi ra tổng tính được.

Example

5
3 4 2 1 3

22