Дана перестановка $$$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
Название |
---|