题目背景

Day 1 Problem A.

题面译自 EGOI2022 subsetmex。

题目描述

一个可重集是元素可以重复出现的集合。例如，$\{0,0,1,2,2,5,5,5,8\}$ 是一个可重集。

给定一个可重集 $S$，值域为 $\N$，和一个目标自然数 $n$（$n\notin S$），你的目标是通过重复进行若干次以下的操作，使得 $n\in S$：

1. 选择一个（可以为空的）子集 $T\subseteq S$，其中 $T$ 不包含重复元素。
2. 在 $S$ 中删除 $T$ 中的元素。（重复元素只删除一个。）
3. 将 $\operatorname{mex}(T)$ 插入 $S$，其中 $\operatorname{mex}(T)$ 是最小的不在 $T$ 中的自然数。$\operatorname{mex}$ 意味着“最小不包含”的值。

你需要求出最少的能使得 $n\in S$ 的操作次数。

由于 $|S|$ 可能很大，它将以一个大小为 $n$ 的列表 $(f_0,\ldots f_{n-1})$ 的形式给出，其中 $f_i$ 代表 $i$ 在 $S$ 中的出现次数。（请回忆 $n$ 是我们想要插入 $S$ 的元素。）

输入格式

第一行一个整数 $t$——数据组数。之后每两行描述一组数据：

• 每组数据的第一行一个整数 $n$，表示要插入 $S$ 的元素。
• 每组数据的第二行 $n$ 个整数 $f_0,f_1,\ldots,f_{n-1}$，按照上述方式描述了集合 $S$。

输出格式

对于每组数据，输出一行一个整数，表示最少操作次数。

2
4
0 3 0 3
5
4 1 0 2 0

4
10

提示

样例 $1$ 解释

初始 $S=\{1,1,1,3,3,3\}$，目标是使得 $4\in S$。我们如下操作：

1. 令 $T=\varnothing$，则 $S=\{0,1,1,1,3,3,3\}$。
2. 令 $T=\{0,1,3\}$，则 $S=\{1,1,2,3,3\}$。
3. 令 $T=\{1\}$，则 $S=\{0,1,2,3,3\}$。
4. 令 $T=\{0,1,2,3\}$，则 $S=\{3,4\}$。

数据范围

对于全部数据，$1\le t\le 200$，$1\le n\le 50$，$0\le f_i\le 10^{16}$。

• 子任务一（$5$ 分）：$n\le 2$。
• 子任务二（$17$ 分）：$n\le 20$。
• 子任务三（$7$ 分）：$f_i=0$。
• 子任务四（$9$ 分）：$f_i\le 1$。
• 子任务五（$20$ 分）：$f_i\le 2\times 10^3$。
• 子任务六（$9$ 分）：$f_0\le 10^{16}$ 且 $\forall j\ne 0,f_j=0$。
• 子任务七（$10$ 分）：$\exists i,f_i\le 10^{16}$ 且 $\forall j\ne i,f_j=0$。
• 子任务八（$23$ 分）：无特殊限制。