Нихат расположил числа $1, 2, ... , n$ в возрастающем порядке. Позже пришел Гусейн и поменял местами некоторые из этих чисел. Теперь у нас имеется некоторая смешанная последовательность $p_1, p_2, ..., p_n$ чисел от $1$ до $n$.

Посчитайте следующую сумму для данной последовательности:

$$ \sum_{l = 1}^N \sum_{r = l}^N min(p_l, p_{l+1}, ..., p_r) $$

Проще говоря, нужно найти сумму всех минимальных чисел во всех подпоследовательностях данной последовательности.

Функция min находит минимальное из данных чисел.

\InputFile

В первой строке дано одно целое число $n$$(1 ≤ n ≤ 10^5)$ - количество чисел в последовательности. Во второй строке следуют $n$ целых чисел $p_i$$(1 ≤ p_i ≤ n)$ - элементы последовательности.

\OutputFile

Вывести требуемую сумму, соответствующую данной последовательности.