排列上的游戏

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Alice 和 Bob 正在玩一个游戏。他们有一个长度为 $n$ 的排列 $p$（长度为 $n$ 的排列是一个长度为 $n$ 的数组，其中每个 $1$ 到 $n$ 的元素恰好出现一次）。他们还有一个筹码，可以放在排列的任意一个元素上。

Alice 和 Bob 轮流行动：Alice 先行动，然后 Bob 行动，然后 Alice，再然后 Bob，依此类推。在第一次行动时，Alice 可以选择排列中的任意一个元素，并将筹码放在该元素上。在接下来的每一次行动中，当前玩家必须将筹码移动到同时满足以下两个条件的任意一个元素上：该元素在当前元素的左侧，并且严格小于当前元素（即如果筹码当前在第 $i$ 个元素上，则可以移动到第 $j$ 个元素上，当且仅当 $j < i$ 且 $p_j < p_i$）。如果某个玩家无法按照游戏规则移动筹码，则该玩家获胜。

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

• 如果 Alice 在她的第一次行动时将筹码放在第 $i$ 个元素上，那么无论 Bob 如何行动，Alice 都能获胜（即 Alice 有必胜策略）。

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

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$）——排列的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。所有 $p_i$ 互不相同。

所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

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

样例输入 1

4
3
2 1 3
2
2 1
3
1 2 3
4
2 1 4 3

样例输出 1

1
0
1
2

数据范围

对于所有数据，$1\le t\le10^4$，$1\le n\le3\times10^5$，$p$ 是 $1$ 到 $n$ 的排列；所有测试用例中 $n$ 的总和不超过 $3\times10^5$。