Going to the Cinema
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 1000
Tags: brute force, greedy, sortings

A company of $$$n$$$ people is planning a visit to the cinema. Every person can either go to the cinema or not. That depends on how many other people will go. Specifically, every person $$$i$$$ said: "I want to go to the cinema if and only if at least $$$a_i$$$ other people will go, not counting myself". That means that person $$$i$$$ will become sad if:

- they go to the cinema, and strictly less than $$$a_i$$$ other people go; or
- they don't go to the cinema, and at least $$$a_i$$$ other people go.

In how many ways can a set of people going to the cinema be chosen so that nobody becomes sad?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of people in the company.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) — integers from peoples' claims.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the number of different ways to choose a set of people going to the cinema so that nobody becomes sad.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, both people want to go to the cinema if and only if the other person goes. There are two valid options: either both people go, or neither of them goes. However, if just one of them goes, both will be sad.

In the second test case, everyone has to go to the cinema. In any other case, someone will be sad.

In the third test case, there are three valid options: person number $$$2$$$ goes to the cinema; or persons with indices $$$2, 3, 4, 7$$$ go; or all eight people go.

Example input:
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

Example output:
2
1
3
2

Editorial:
Let's fix the number of people going to the cinema $$$k$$$ and try to choose a set of this exact size. What happens to people with different $$$a_i$$$?
• If $$$a_i < k$$$, person $$$i$$$ definitely wants to go.
• If $$$a_i > k$$$, person $$$i$$$ definitely does not want to go.
• If $$$a_i = k$$$, there is actually no good outcome for person $$$i$$$. If person $$$i$$$ goes to the cinema, there are only $$$k - 1$$$ other people going, so person $$$i$$$ will be sad (since $$$k - 1 < a_i$$$). If person $$$i$$$ does not go, there are $$$k$$$ other people going, so person $$$i$$$ will be sad too (since $$$k \ge a_i$$$).
Thus, for a set of size $$$k$$$ to exist, there must be no people with $$$a_i = k$$$, and the number of people with $$$a_i < k$$$ must be exactly $$$k$$$. We can easily check these conditions if we use an auxiliary array cnt such that cnt[x] is equal to the number of people with $$$a_i = x$$$.
Alternative solution:
Notice that if a set of $$$k$$$ people can go to the cinema, it must always be a set of people with the smallest $$$a_i$$$. Thus, we can start with sorting the array $$$a$$$ in non-decreasing order.
Then, for each length $$$k$$$ of a prefix of this array, we can check whether the first $$$k$$$ elements are all smaller than $$$k$$$, and the remaining $$$n-k$$$ elements are all greater than $$$k$$$.
However, since the array is sorted, it is enough to check that the $$$k$$$-th element is smaller than $$$k$$$, and the $$$k+1$$$-th element is greater than $$$k$$$.