Độ lệch của mảng

Cho mảng $a$ gồm $n$ phần tử.

Với một đoạn con liên tiếp bất kỳ của mảng, độ lệch của đoạn đó được định nghĩa là hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất trong đoạn.

Độ lệch của mảng là tổng độ lệch của tất cả các đoạn con liên tiếp của mảng đó.

Ví dụ, mảng $[1,4,1]$ có $6$ đoạn con liên tiếp với các độ lệch lần lượt là $0$, $3$, $3$, $0$, $3$, $0$, nên độ lệch của mảng bằng $9$.

Hãy tính độ lệch của mảng $a$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, kích thước của mảng $a$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, các phần tử của mảng.

Dữ liệu ra

In ra một số nguyên duy nhất là độ lệch của mảng $a$.

Ràng buộc

• $1\le n\le {10}^6$
• $1\le a_i\le {10}^6$

Ví dụ