P17280 The Promise to Fly into the Sky.

"Even if we do not look up at the starry sky, it is always watching us."

Countless jellyfish that once traveled with you have turned into tiny starlight and slowly risen into the boundless night sky. They can be represented as $n$ points on an infinitely long number line, where the $i$-th point is initially at $a_i$. Multiple points may be at the same position. Index wants to perform at most $10^{218105633}$ **evolutions** on these points (the number of times can be $0$). In one **evolution**, she will: 1. Choose a position $x$ that currently contains at least two points. 2. Decrease the number of points at $x$ by $2$. 3. Increase the number of points at $x-1$ and $x+1$ by $1$ each. Index wants to know the maximum possible value of the $\operatorname{mex}$ of the set formed by the positions of all points after the operations finish. --- Note: For an integer set $S$, $\operatorname{mex}(S)$ is defined as the smallest non-negative integer that does not belong to $S$.

The first line contains an integer $T$, the number of testdata groups. For each testdata group: The first line contains an integer $n$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the initial positions of the points.

For each testdata group, output one integer per line, representing the maximum $\operatorname{mex}$ that can be achieved.

One possible sequence of operations is: $$ \{1,1,2,2\}\to\{0,2,2,2\}\to\{0,1,2,3\}. $$ At this time, the positions of all points are $\{0,1,2,3\}$, and its $\operatorname{mex}$ is $4$. It can be proven that the answer cannot be larger.  --- Constraints (for all testdata): $1\le n,\sum n\le 5\times 10^5,0\le a_i\le 10^9$。 ::cute-table{tuack} | Test Point ID | $n,\sum n\leq$ | $a_i\leq$ | Special Property | | :----------: | :------------: | :-------: | :--------------: | | $1\sim 3$ | $80$ | $8$ | None | | $4\sim 9$ | $2000$ | $2000$ | ^ | | $10\sim 13$ | $5\times 10^4$ | $5\times 10^4$ | ^ | | $14,15$ | ^ | $10^9$ | ^ | | $16,17$ | $5\times 10^5$ | ^ | A | | $18\sim 25$ | ^ | ^ | None | Special Property A: All $a_i$ are guaranteed to be the same. # Input Format # Output Format # Hint Translated by ChatGPT 5