Дан массив a, состоящий из n элементов. Назовём дисбалансом некоторого подотрезка массива разность между максимумом и минимумом на этом подотрезке. Дисбаланс всего массива — сумма дисбалансов всех подотрезков этого массива.
Например, дисбаланс массива [1, 4, 1] равен 9, так как его 6 подотрезков имеют следующий дисбаланс:
- [1] (с позиции 1 до позиции 1), дисбаланс равен 0;
- [1, 4] (с позиции 1 до позиции 2), дисбаланс равен 3;
- [1, 4, 1] (с позиции 1 до позиции 3), дисбаланс равен 3;
- [4] (с позиции 2 до позиции 2), дисбаланс равен 0;
- [4, 1] (с позиции 2 до позиции 3), дисбаланс равен 3;
- [1] (с позиции 3 до позиции 3), дисбаланс равен 0;
Ваша задача — вычислить дисбаланс массива a.
Выходные данные
Выведите одно целое число — дисбаланс массива a.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 4 1
|
9
|