Codeforces Round 901 (Div. 2) |
---|
Finished |
You are given an array of $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$.
Let $$$m$$$ be a variable that is initialized to $$$0$$$, Jellyfish will perform the following operation $$$n$$$ times:
Now Jellyfish wants to know the minimum possible final value of $$$m$$$ if he performs all the operations optimally.
$$$^{\dagger}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 5000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the size of the array.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the integers in the array.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.
For each test case, output a single integer — the minimum value of $$$m$$$ if the operations are performed optimally.
485 2 1 0 3 0 4 021 251 0 2 114514 080 1 2 0 1 2 0 3
3 0 2 7
In the first test case, we delete elements from $$$a$$$ in the following order: $$$[5,2,\color{red}{1},0,3,0,4,0] \to [5,2,0,3,\color{red}{0},4,0] \to [5,2,\color{red}{0},3,4,0] \to [5,2,3,4,\color{red}{0}] \to [5,2,\color{red}{3},4] \to [\color{red}{5},2,4] \to [\color{red}{2},4] \to [\color{red}{4}] \to [~]$$$. The value of $$$m$$$ will be $$$1+1+1+0+0+0+0+0=3$$$.
Name |
---|