Найдите сумму разбросов для всех подотрезков заданной последовательности

Назовем разбросом последовательности чисел разницу между максимальным и минимальным значением в этой последовательности. Для последовательности 3, 5, 7, 4 разброс будет равен 4 (7 - 3), а для последовательности 17, 17 разброс будет равен 0 (17 - 17).

Найдите сумму разбросов для всех подотрезков заданной последовательности. Подотрезком называется последовательность подряд идущих элементов.

Формат входных данных

В первой строке вводится число n (2 ≤ n ≤ 300000) - длина последовательности.

В следующих n строках вводятся числа ai (1 ≤ ai ≤ 108) - элементы последовательности.

Формат результата

Выведите ответ на задачу.

Примеры

Входные данные

3

1

2

3

Результат работы

4

Входные данные

4

7

5

7

5

Результат работы

12

Входные данные

4

3

1

7

2

Результат работы

31

Примечания

Подотрезки длины 1 дают разброс, равный нулю.

В первом примере подотрезки (1, 2), (2, 3) и (1, 2, 3) дают разброс 1, 1 и 2 соответственно. Сумма равна 4.

Во втором примере следующие отрезки и соответствующие им разбросы:

(7, 5) - 2, (5, 7) - 2, (7, 5) - 2, (7, 5, 7) - 2, (5, 7, 5) - 2, (7, 5, 7, 5) - 2

Сумма разбросов равна 12.