Codeforces Round 645 (Div. 2) |
---|
Finished |
Maria is the most active old lady in her house. She was tired of sitting at home. She decided to organize a ceremony against the coronavirus.
She has $$$n$$$ friends who are also grannies (Maria is not included in this number). The $$$i$$$-th granny is ready to attend the ceremony, provided that at the time of her appearance in the courtyard there will be at least $$$a_i$$$ other grannies there. Note that grannies can come into the courtyard at the same time. Formally, the granny $$$i$$$ agrees to come if the number of other grannies who came earlier or at the same time with her is greater than or equal to $$$a_i$$$.
Grannies gather in the courtyard like that.
Your task is to find what maximum number of grannies (including herself) Maria can collect in the courtyard for the ceremony. After all, the more people in one place during quarantine, the more effective the ceremony!
Consider an example: if $$$n=6$$$ and $$$a=[1,5,4,5,1,9]$$$, then:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then test cases follow.
The first line of a test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of grannies (Maria is not included in this number).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$).
It is guaranteed that the sum of the values $$$n$$$ over all test cases of the input does not exceed $$$10^5$$$.
For each test case, print a single integer $$$k$$$ ($$$1 \le k \le n + 1$$$) — the maximum possible number of grannies in the courtyard.
4 5 1 1 2 2 1 6 2 3 4 5 6 7 6 1 5 4 5 1 9 5 1 2 3 5 6
6 1 6 4
In the first test case in the example, on the first step Maria can call all the grannies. Then each of them will see five grannies when they come out. Therefore, Maria and five other grannies will be in the yard.
In the second test case in the example, no one can be in the yard, so Maria will remain there alone.
The third test case in the example is described in the details above.
In the fourth test case in the example, on the first step Maria can call grannies with numbers $$$1$$$, $$$2$$$ and $$$3$$$. If on the second step Maria calls $$$4$$$ or $$$5$$$ (one of them), then when a granny appears in the yard, she will see only four grannies (but it is forbidden). It means that Maria can't call the $$$4$$$-th granny or the $$$5$$$-th granny separately (one of them). If she calls both: $$$4$$$ and $$$5$$$, then when they appear, they will see $$$4+1=5$$$ grannies. Despite the fact that it is enough for the $$$4$$$-th granny, the $$$5$$$-th granny is not satisfied. So, Maria cannot call both the $$$4$$$-th granny and the $$$5$$$-th granny at the same time. That is, Maria and three grannies from the first step will be in the yard in total.
Name |
---|