P17280 飞向天空的约定
题目背景
「就算我们不抬头仰望，星空，也永远注视着我们。」
题目描述
无数曾伴你同行的水母化作了点点星光，缓缓升入无垠的夜空。它们可以用无限长的数轴上的 $n$ 个点表示，第 $i$ 个点初始位于 $a_i$。同一个位置可以有多个点。
Index 想要对这些点进行最多 $10^{218105633}$ 次**演化**（次数可以为 $0$），在一次**演化**中，她会：
1. 选择一个当前至少包含两个点的位置 $x$；
2. 将 $x$ 处的点数量减少 $2$；
3. 将 $x-1$ 和 $x+1$ 处的点数量各增加 $1$。
Index 想知道在操作结束后，所有的点的位置构成的集合的 $\operatorname{mex}$ 的最大可能值。
---
注：对于一个整数集合 $S$，$\operatorname{mex}(S)$ 定义为最小的不属于 $S$ 的非负整数。
输入格式
第一行包含一个整数 $T$，表示测试数据组数。
对于每组测试数据：
第一行包含一个整数 $n$。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个点的初始位置。
输出格式
对于每组测试数据，输出一行一个整数，表示可达到的最大 $\operatorname{mex}$。
说明/提示
一种操作方式为
$$
\{1,1,2,2\}\to\{0,2,2,2\}\to\{0,1,2,3\}.
$$
此时所有点的位置为 $\{0,1,2,3\}$，其 $\operatorname{mex}$ 为 $4$。可以证明答案不可能更大。
---
对于所有测试数据，保证：
$1\le n,\sum n\le 5\times 10^5,0\le a_i\le 10^9$。
::cute-table{tuack}
| 测试点编号 | $n,\sum n\leq$ | $a_i\leq$ | 特殊性质 |
| :--------: | :-------------: | :-------: | :------: |
| $1\sim 3$ | $80$ | $8$ | 无 |
| $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$ | ^ | ^ | 无 |
特殊性质 A：保证所有 $a_i$ 相同。