310615: CF1860C. Game on Permutation
Description
Alice and Bob are playing a game. They have a permutation $p$ of size $n$ (a permutation of size $n$ is an array of size $n$ where each element from $1$ to $n$ occurs exactly once). They also have a chip, which can be placed on any element of the permutation.
Alice and Bob make alternating moves: Alice makes the first move, then Bob makes the second move, then Alice makes the third move, and so on. During the first move, Alice chooses any element of the permutation and places the chip on that element. During each of the next moves, the current player has to move the chip to any element that is simultaneously to the left and strictly less than the current element (i. e. if the chip is on the $i$-th element, it can be moved to the $j$-th element if $j < i$ and $p_j < p_i$). If a player cannot make a move (it is impossible to move the chip according to the rules of the game), that player wins the game.
Let's say that the $i$-th element of the permutation is lucky if the following condition holds:
- if Alice places the chip on the $i$-th element during her first move, she can win the game no matter how Bob plays (i. e. she has a winning strategy).
You have to calculate the number of lucky elements in the permutation.
InputThe first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) – the number of elements in the permutation.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). All $p_i$ are distinct.
The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.
OutputFor each test case, print a single integer — the number of lucky elements in the permutation.
ExampleInput4 3 2 1 3 2 2 1 3 1 2 3 4 2 1 4 3Output
1 0 1 2Note
In the first test case of the example, the $3$-rd element of the permutation is lucky.
In the second test case of the example, there are no lucky elements.
In the third test case of the example, the $2$-nd element of the permutation is lucky.
In the fourth test case of the example, the $3$-rd and the $4$-th element of the permutation are lucky.
Output
Alice和Bob在玩一个游戏。他们有一个大小为n的排列p（大小为n的排列是一个大小为n的数组，其中每个元素从1到n恰好出现一次）。他们还有一个筹码，可以放在排列的任何元素上。
Alice和Bob轮流进行操作：Alice先进行第一次操作，然后Bob进行第二次操作，接着Alice进行第三次操作，以此类推。在第一次操作时，Alice可以选择排列中的任何元素并将筹码放在该元素上。在接下来的每次操作中，当前玩家**必须**将筹码移动到同时位于当前元素左侧且严格小于当前元素的位置（即如果筹码在第i个元素上，可以将其移动到第j个元素，如果j
如果排列的第i个元素满足以下条件，则该元素是**幸运的**：
- 如果Alice在第一次操作时将筹码放在第i个元素上，无论Bob如何操作，她都能获胜（即她有必胜策略）。
计算排列中幸运元素的数量。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤3×10^5）——排列中的元素数量。
- 第二行包含n个整数p_1, p_2, …, p_n（1≤p_i≤n）。所有p_i都是不同的。
- 所有测试用例的n之和不超过3×10^5。
输出：
- 对于每个测试用例，打印一个整数——排列中幸运元素的数量。
示例：
输入：
```
4
3
2 1 3
2
2 1
3
1 2 3
4
2 1 4 3
```
输出：
```
1
0
1
2
```
说明：
- 在第一个测试用例中，排列的第三个元素是幸运的。
- 在第二个测试用例中，没有幸运元素。
- 在第三个测试用例中，排列的第二个元素是幸运的。
- 在第四个测试用例中，排列的第三个和第四个元素是幸运的。题目大意： Alice和Bob在玩一个游戏。他们有一个大小为n的排列p（大小为n的排列是一个大小为n的数组，其中每个元素从1到n恰好出现一次）。他们还有一个筹码，可以放在排列的任何元素上。 Alice和Bob轮流进行操作：Alice先进行第一次操作，然后Bob进行第二次操作，接着Alice进行第三次操作，以此类推。在第一次操作时，Alice可以选择排列中的任何元素并将筹码放在该元素上。在接下来的每次操作中，当前玩家**必须**将筹码移动到同时位于当前元素左侧且严格小于当前元素的位置（即如果筹码在第i个元素上，可以将其移动到第j个元素，如果j