C. Игра с перестановкой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть перестановка $$$p$$$ размера $$$n$$$ (перестановка размера $$$n$$$  — это массив размера $$$n$$$, где каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз). Также у них есть фишка, которую можно разместить на любом элементе перестановки.

Алиса и Боб делают ходы поочередно: Алиса делает первый ход, затем Боб делает второй ход, затем Алиса делает третий ход и так далее. Во время первого хода Алиса выбирает любой элемент перестановки и ставит фишку на этот элемент. Во время каждого из следующих ходов текущий игрок должен переместить фишку на элемент, который одновременно находится слева и строго меньше текущего элемента (т.е. если фишка находится на $$$i$$$-м элементе, она может быть перемещена на $$$j$$$-й элемент, если $$$j < i$$$ и $$$p_j < p_i$$$). Если игрок не может сделать ход (переместить фишку в соответствии с правилами игры невозможно), этот игрок выигрывает в игре.

Скажем, что $$$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$$$.

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

Для каждого набора входных данных выведите одно целое число — количество счастливых элементов в перестановке.

Пример
Входные данные
4
3
2 1 3
2
2 1
3
1 2 3
4
2 1 4 3
Выходные данные
1
0
1
2
Примечание

В первом наборе входных данных из примера $$$3$$$-й элемент — счастливый.

Во втором наборе входных данных из примера нет счастливых элементов.

В третьем наборе входных данных из примера $$$2$$$-й элемент — счастливый.

В четвертом наборе входных данных из примера $$$3$$$-й и $$$4$$$-й элемент — счастливые.