Ніхат розташував числа $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

Вивести необхідну суму, що відповідає даній послідовності.