問題一覧 > 通常問題

No.3780 Erase and Mex

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : askr58 / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 13698 / 自分の提出
問題文最終更新日: 2026-10-30 17:11:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 520 (順位表) の他の問題:

Problem Statement

There are $N$ non-negative integers written on a blackboard. Let the $i$-th integer be $A_i$. You may perform the following operation any number of times, possibly $0$ times.

  • Choose any number of integers, at least $1$, written on the blackboard. Let $S$ be the multiset consisting of the chosen integers. Write one $\operatorname{mex}(S)$ on the blackboard, and then erase all of the chosen integers from the blackboard.

Here, $\operatorname{mex}(S)$ denotes the smallest non-negative integer not contained in $S$.

Also, you may make an end declaration exactly once, at any time of your choice. When you make the end declaration, if exactly $1$ integer is written on the blackboard at that point, you obtain $x$ points, where $x$ is that integer; otherwise, you obtain $-10^{100}$ points. Find the maximum score you can obtain.

Answer for $T$ test cases.

Constraints

  • $1\le T\le 2\times 10^5$
  • $1\le N\le 2 \times 10^5$
  • $0\le A_i\le 10^9 (1\le i\le N)$
  • The sum of $N$ over the $T$ test cases is at most $2\times 10^5$
  • All input values are integers

Input

The input is given in the following format, where $case_i$ denotes the $i$-th test case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

$N$
$A_1\ A_2\ \cdots\ A_N$

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

Sample

Sample 1
Input
2
6
3 1 1 1 1 1
20
21 10 19 3 11 24 12 6 24 17 4 3 20 11 9 3 23 0 22 9
Output
4
7

For the $1$st test case, you can obtain $4$ points by performing the operations as follows.

  • Let $S=\{1,1\}$. Since $\operatorname{mex}(S)=0$, the integers written on the blackboard become $\{0,1,1,1,3\}$.
  • Let $S=\{1\}$. Since $\operatorname{mex}(S)=0$, the integers written on the blackboard become $\{0,0,1,1,3\}$.
  • Let $S=\{0,1\}$. Since $\operatorname{mex}(S)=2$, the integers written on the blackboard become $\{0,1,2,3\}$.
  • Let $S=\{0,1,2,3\}$. Since $\operatorname{mex}(S)=4$, the integers written on the blackboard become $\{4\}$.
  • Make the end declaration.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。