Алиса и Боб играют в игру. У них есть перестановка $$$p$$$ размера $$$n$$$ (перестановка размера $$$n$$$ — это массив размера $$$n$$$, где каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз). Также у них есть фишка, которую можно разместить на любом элементе перестановки.
Алиса и Боб делают ходы поочередно: Алиса делает первый ход, затем Боб делает второй ход, затем Алиса делает третий ход и так далее. Во время первого хода Алиса выбирает любой элемент перестановки и ставит фишку на этот элемент. Во время каждого из следующих ходов текущий игрок должен переместить фишку на элемент, который одновременно находится слева и строго меньше текущего элемента (т.е. если фишка находится на $$$i$$$-м элементе, она может быть перемещена на $$$j$$$-й элемент, если $$$j < i$$$ и $$$p_j < p_i$$$). Если игрок не может сделать ход (переместить фишку в соответствии с правилами игры невозможно), этот игрок выигрывает в игре.
Скажем, что $$$i$$$-й элемент перестановки счастливый, если выполняется следующее условие:
Ваша задача — посчитайте количество счастливых элементов в перестановке.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество элементов в перестановке.
Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). Все $$$p_i$$$ различны.
Сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество счастливых элементов в перестановке.
432 1 322 131 2 342 1 4 3
1 0 1 2
В первом наборе входных данных из примера $$$3$$$-й элемент — счастливый.
Во втором наборе входных данных из примера нет счастливых элементов.
В третьем наборе входных данных из примера $$$2$$$-й элемент — счастливый.
В четвертом наборе входных данных из примера $$$3$$$-й и $$$4$$$-й элемент — счастливые.
Название |
---|