Educational Codeforces Round 23 |
---|
Закончено |
Дан массив a, состоящий из n элементов. Назовём дисбалансом некоторого подотрезка массива разность между максимумом и минимумом на этом подотрезке. Дисбаланс всего массива — сумма дисбалансов всех подотрезков этого массива.
Например, дисбаланс массива [1, 4, 1] равен 9, так как его 6 подотрезков имеют следующий дисбаланс:
Ваша задача — вычислить дисбаланс массива a.
Первая строка содержит единственное целое число n (1 ≤ n ≤ 106) — размер массива a.
Во второй строке записаны n целых чисел a1, a2... an (1 ≤ ai ≤ 106) — элементы массива.
Выведите одно целое число — дисбаланс массива a.
3
1 4 1
9
Название |
---|