Для перестановки p чисел від 1 до n, визначимо f(p) наступним чином: для кожної пари чисел (i,j) з 1≤i≤j≤n, порахуємо пару (min,max), де min — найменше число серед чисел ai,ai+1,…,aj, а max — найбільше з них. Тоді f(p) рівна кількості різних пар серед всіх 2n(n+1) пар.
Наприклад розглянемо перестановку (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) для даної вам перестановки (p1,p2,…,pn).
Перший рядок вхідних даних містить єдине число n (1≤n≤2⋅105).
Другий рядок вхідних даних містить n цілих чисел p1,p2,…,pn (1≤pi≤n, pi попарно різні) — перестановку довжини n.
Виведіть f(p).
Перший приклад розібрано в умові.