Background

Day 1 Problem A.

The statement is translated from EGOI2022 subsetmex。

Problem Description

A multiset is a set in which elements may appear multiple times. For example, $\{0,0,1,2,2,5,5,5,8\}$ is a multiset.

You are given a multiset $S$ with values in $\N$, and a target natural number $n$ ($n\notin S$). Your goal is to make $n\in S$ by repeatedly performing the following operation some number of times:

1. Choose a (possibly empty) subset $T\subseteq S$, where $T$ contains no duplicate elements.
2. Delete the elements of $T$ from $S$. (If an element appears multiple times, remove only one copy.)
3. Insert $\operatorname{mex}(T)$ into $S$, where $\operatorname{mex}(T)$ is the smallest natural number that is not in $T$. $\operatorname{mex}$ stands for “minimum excluded value”.

You need to find the minimum number of operations needed to make $n\in S$.

Since $|S|$ can be very large, it is given as a list of length $n$, $(f_0,\ldots f_{n-1})$, where $f_i$ denotes how many times $i$ appears in $S$. (Recall that $n$ is the element we want to insert into $S$.)

Input Format

The first line contains an integer $t$, the number of test cases. Then each test case is described in two lines:

• The first line of each test case contains an integer $n$, the element to be inserted into $S$.
• The second line contains $n$ integers $f_0,f_1,\ldots,f_{n-1}$, describing the multiset $S$ as above.

Output Format

For each test case, output one line containing one integer, the minimum number of operations.

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

4
10

Hint

Explanation for Sample $1$.

Initially, $S=\{1,1,1,3,3,3\}$, and the goal is to make $4\in S$. We can do the following operations:

1. Let $T=\varnothing$, then $S=\{0,1,1,1,3,3,3\}$.
2. Let $T=\{0,1,3\}$, then $S=\{1,1,2,3,3\}$.
3. Let $T=\{1\}$, then $S=\{0,1,2,3,3\}$.
4. Let $T=\{0,1,2,3\}$, then $S=\{3,4\}$.

Constraints

For all testdata, $1\le t\le 200$, $1\le n\le 50$, $0\le f_i\le 10^{16}$.

• Subtask 1 ($5$ points): $n\le 2$.
• Subtask 2 ($17$ points): $n\le 20$.
• Subtask 3 ($7$ points): $f_i=0$.
• Subtask 4 ($9$ points): $f_i\le 1$.
• Subtask 5 ($20$ points): $f_i\le 2\times 10^3$.
• Subtask 6 ($9$ points): $f_0\le 10^{16}$ and $\forall j\ne 0,f_j=0$.
• Subtask 7 ($10$ points): $\exists i,f_i\le 10^{16}$ and $\forall j\ne i,f_j=0$.
• Subtask 8 ($23$ points): No special constraints.

Input Format

Output Format

Translated by ChatGPT 5