Дан массив 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.