E. Максимум справа от минимума
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка $$$p$$$ длины $$$n$$$ — массив, состоящий из целых чисел от $$$1$$$ до $$$n$$$, все различные.

Пусть $$$p_{l,r}$$$ задает подмассив — массив, полученный при выписывании элементов с позиции $$$l$$$ по позицию $$$r$$$, включительно.

Пусть $$$\mathit{maxpos}_{l,r}$$$ задает позицию максимального элемента на $$$p_{l,r}$$$. Аналогично, пусть $$$\mathit{minpos}_{l,r}$$$ задает позицию минимального элемента на нем.

Посчитайте количество подмассивов $$$p_{l,r}$$$ таких, что $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$$$.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). Все $$$p_i$$$ различны.

Выходные данные

Выведите одно целое число — количество подмассивов $$$p_{l,r}$$$ таких, что $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$$$.

Примеры
Входные данные
3
1 2 3
Выходные данные
3
Входные данные
6
5 3 6 1 4 2
Выходные данные
4
Входные данные
10
5 1 6 2 8 3 4 10 9 7
Выходные данные
38