Коровы Фермера Джона имеют высоты \(1, 2, \ldots, N\). Однажды выстроились в ряд
в некотором порядке для игры в фрисби. Пусть \(h_1 \ldots h_N\) обозначают высоты
этих коров в заданном порядке (поэтому \(h\)'-ки есть перестановка чисел \(1 \ldots N\)).
Две коровы на позициях \(i\) и \(j\) в строке могут успешно бросить фрисби друг другу,
если и только если все коровы между ними имеют рост меньше чем \(\min(h_i, h_j)\).
Вычислите сумму расстояний между всеми парами позиций \(i<j\), которые ограничены
парой коров, которые могут бросить которые могу успешно бросать фрисби друг другу.
Расстояние между позициями \(i\) и \(j\) есть \(j-i+1\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит одно целое число \(N\). Следующая строка ввода
содержит \(h_1 \ldots h_N\), разделённые одиночными пробелами.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите сумму расстояний для всех пар позиций в которых коровы могут бросить
фрисби друг другу. Для ответа используйте 64-битное целое (например, "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
4 3 1 2 5 6 7
|
24
|