← 返回题目列表

Codeforces · 1860/C

C. 排列游戏

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩游戏。它们具有大小为 $$$n$$$ 的排列 $$$p$$$(大小为 $$$n$$$ 的排列是大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次)。它们还有一个芯片,可以放置在排列的任何元素上。

Alice 和 Bob 交替移动:Alice 移动第一个移动,然后 Bob 移动第二个移动,然后 Alice 移动第三个移动,依此类推。在第一步中,爱丽丝选择排列中的任何元素并将筹码放在该元素上。在接下来的每次移动中,当前玩家必须将筹码移动到同时向左且严格小于当前元素的任何元素(即,如果筹码位于第 $$$i$$$ 元素上,则如果 $$$j < i$$$ 且 $$$p_j < p_i$$$ 则可以将其移动到第 $$$j$$$ 元素)。如果玩家无法移动(根据游戏规则不可能移动筹码),则该玩家赢得游戏。

假设如果满足以下条件,则排列的第 $$$i$$$ 元素是幸运的:

- 如果 Alice 在第一步中将筹码放在第 $$$i$$$ 个元素上,那么无论 Bob 如何玩,她都可以赢得游戏(即她有获胜策略)。

你必须计算排列中幸运元素的数量。

输入

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

输出

对于每个测试用例,打印一个整数 - 排列中幸运元素的数量。

示例

输入 #1

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

输出 #1

1
0
1
2

注意

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

在示例的第二个测试用例中,没有幸运元素。

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

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