Для перестановки $p$ чисел від $1$ до $n$, визначимо $f(p)$ наступним чином: для кожної пари чисел $(i, j)$ з $1 \le i \le j \le n$, порахуємо пару $(min, max)$, де $min$ --- найменше число серед чисел $a_i, a_{i+1}, \ldots, a_j$, а $max$ --- найбільше з них. Тоді $f(p)$ рівна кількості різних пар серед всіх $\frac{n(n+1)}{2}$ пар. Наприклад розглянемо перестановку $(1, 3, 2)$. \begin{itemize} \item Для пари $(1, 1)$, $(min, max) = (1, 1)$ \item Для пари $(1, 2)$, $(min, max) = (1, 3)$ \item Для пари $(1, 3)$, $(min, max) = (1, 3)$ \item Для пари $(2, 2)$, $(min, max) = (3, 3)$ \item Для пари $(2, 3)$, $(min, max) = (2, 3)$ \item Для пари $(3, 3)$, $(min, max) = (2, 2)$ \end{itemize} Всього $5$ різних пар, тому $f((1, 3, 2)) = 5$. Знайдіть $f(p)$ для даної вам перестановки $(p_1, p_2, \ldots, p_n)$. \InputFile Перший рядок вхідних даних містить єдине число $n$ ($1 \le n \le 2\cdot 10^5$). Другий рядок вхідних даних містить $n$ цілих чисел $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, $p_i$ \textbf{попарно різні}) --- перестановку довжини $n$. \OutputFile Виведіть $f(p)$. \Note Перший приклад розібрано в умові.