bababooey

题目描述

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

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

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

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

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

输入格式

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

提示

在第一个样例中，排列的第 $3$ 个元素是幸运的。

在第二个样例中，没有幸运元素。

在第三个样例中，排列的第 $2$ 个元素是幸运的。

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