题目描述

有一个由 $n$ 个人组成的公司计划一起去看电影。每个人可以选择去电影院，也可以选择不去。这取决于有多少其他人会去。具体来说，每个人 $i$ 说：“只有当至少有 $a_i$ 个其他人去（不包括我自己）时，我才想去电影院。” 这意味着，如果出现以下情况，$i$ 就会感到难过：

• 他去了电影院，但去的人中（不包括他自己）严格少于 $a_i$ 个；
• 他没有去电影院，但去的人中（不包括他自己）至少有 $a_i$ 个。

问有多少种选择去电影院的人集合的方法，使得没有人感到难过？

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每组测试数据包含两行。第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示公司的人数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le n - 1$），表示每个人的要求。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示有多少种不同的方法选择去电影院的人集合，使得没有人感到难过。

说明/提示

在第一个测试用例中，两个人都希望只有当另一个人也去时才去电影院。有两种有效方案：要么两个人都去，要么两个人都不去。如果只有一个人去，两个人都会感到难过。

在第二个测试用例中，所有人都必须去电影院。否则，至少会有一个人感到难过。

在第三个测试用例中，有三种有效方案：第 $2$ 个人去电影院；第 $2, 3, 4, 7$ 个人去电影院；或者所有 $8$ 个人都去。

由 ChatGPT 4.1 翻译

样例

4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3

2
1
3
2