ПерестановочкА

Для перестановки $p$ чисел від $1$ до $n$, визначимо $f(p)$ наступним чином: для кожної пари чисел $(i,j)$ з $1\le i\le j\le n$, порахуємо пару $(min,max)$, де $min$ — найменше число серед чисел $a_i,a_{i+1},\dots ,a_j$, а $max$ — найбільше з них. Тоді $f(p)$ рівна кількості різних пар серед всіх $\frac{n(n+1)}{2}$ пар.

Наприклад розглянемо перестановку $(1,3,2)$.

• Для пари $(1,1)$, $(min,max)=(1,1)$

• Для пари $(1,2)$, $(min,max)=(1,3)$

• Для пари $(1,3)$, $(min,max)=(1,3)$

• Для пари $(2,2)$, $(min,max)=(3,3)$

• Для пари $(2,3)$, $(min,max)=(2,3)$

• Для пари $(3,3)$, $(min,max)=(2,2)$

Всього $5$ різних пар, тому $f((1,3,2))=5$.

Знайдіть $f(p)$ для даної вам перестановки $(p_1,p_2,\dots ,p_n)$.

Input

Перший рядок вхідних даних містить єдине число $n$ ($1\le n\le 2\cdot 10^5$).

Другий рядок вхідних даних містить $n$ цілих чисел $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$, $p_i$ попарно різні) — перестановку довжини $n$.

Output

Виведіть $f(p)$.

Examples

Note

Перший приклад розібрано в умові.