Дана последовательность $$$a$$$ из $$$n$$$ различных чисел. Назовём отрезок $$$[l,r]$$$ годным, если крайние элементы с этого отрезка ($$$a_l$$$ и $$$a_r$$$) являются максимальным и минимальным элементами с отрезка.
Ваша задача — посчитать годноту последовательности $$$a$$$, то есть количество таких $$$1 \leq l \leq r \leq n$$$, что отрезок $$$[l,r]$$$ является годным.
Первая строка содержит целое число $$$n$$$ — размер последовательности ($$$1 \leq n \leq 10^6$$$).
Вторая строка содержит $$$n$$$ различных чисел $$$a_i$$$, разделённых пробелом ($$$1 \leq a_i \leq n$$$).
Выведите единственное число — ответ на задачу.
3
1 2 3
6
5
4 2 5 3 1
10
