D. Несбалансированный массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Первая строка содержит единственное целое число n (1 ≤ n ≤ 106) — размер массива a.

Во второй строке записаны n целых чисел a1, a2... an (1 ≤ ai ≤ 106) — элементы массива.

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

Выведите одно целое число — дисбаланс массива a.

Пример
Входные данные
3
1 4 1
Выходные данные
9