CF1860C.Game on Permutation

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 \lt i$ and $p_j \lt 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.

Alice 和 Bob 正在进行一场游戏。他们有一个长度为 $n$ 的排列 $p$（长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中 $1$ 到 $n$ 的每个整数恰好出现一次）。他们还有一枚棋子，可以放置在排列的任意一个元素上。

Alice 和 Bob 轮流进行操作：Alice 先手，接着 Bob 进行第二步，然后 Alice 进行第三步，依此类推。在第一步中，Alice 可以任选排列中的一个元素，并将棋子放在该元素上。在之后的每一步中，当前玩家必须将棋子移动到某个同时满足以下两个条件的元素上：

• 位于当前元素的左侧（即下标更小）；
• 其值严格小于当前元素的值。
  （即：若棋子当前位于第 $i$ 个元素上，则它可以被移动到第 $j$ 个元素上，当且仅当 $j \lt i$ 且 $p_j \lt p_i$。）
  若某位玩家无法进行合法移动（即不存在满足上述规则的可移动位置），则该玩家获胜。

我们称排列中的第 $i$ 个元素是幸运的，如果满足以下条件：

• 若 Alice 在第一步时将棋子放在第 $i$ 个元素上，则无论 Bob 如何应对，Alice 都必胜（即 Alice 存在必胜策略）。

你需要计算该排列中幸运元素的个数。

The 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$.

第一行包含一个整数 $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$。

For each test case, print a single integer — the number of lucky elements in the permutation.

对于每个测试用例，输出一个整数——即排列中幸运元素的个数。

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.

在示例的第一个测试用例中，排列的第 $3$ 个元素是幸运元素。

在示例的第二个测试用例中，不存在幸运元素。

在示例的第三个测试用例中，排列的第 $2$ 个元素是幸运元素。

在示例的第四个测试用例中，排列的第 $3$ 个和第 $4$ 个元素是幸运元素。