CF2049A MEX Destruction

Evirir the dragon snuck into a wizard's castle and found a mysterious contraption, and their playful instincts caused them to play with (destroy) it... Evirir the dragon found an array $ a_1, a_2, \ldots, a_n $ of $ n $ non-negative integers. In one operation, they can choose a non-empty subarray $ ^{\text{∗}} $ $ b $ of $ a $ and replace it with the integer $ \operatorname{mex}(b) $ $ ^{\text{†}} $ . They want to use this operation any number of times to make $ a $ only contain zeros. It can be proven that this is always possible under the problem constraints. What is the minimum number of operations needed? $ ^{\text{∗}} $ An array $ c $ is a subarray of an array $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. $ ^{\text{†}} $ The minimum excluded (MEX) of a collection of integers $ f_1, f_2, \ldots, f_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ f $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 200 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 50 $ ), the length of $ a $ . The second line of each test case contains $ n $ space-separated integers, $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 100 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 500 $ .

For each test case, output a single integer on a line, the minimum number of operations needed to make $ a $ contain only zeros.

In the first test case, Evirir can choose the subarray $ b = [1, 2, 3] $ and replace it with $ \operatorname{mex}(1, 2, 3) = 0 $ , changing $ a $ from $ [0, \underline{1, 2, 3}] $ to $ [0, 0] $ (where the chosen subarray is underlined). Therefore, the answer is $ 1 $ . In the second test case, $ a $ already contains only $ 0 $ s, so no operation is needed. In the third test case, Evirir can change $ a $ as follows: $ [1, \underline{0, 1, 0, 1}] \to [\underline{1, 2}] \to [0] $ . Here, $ \operatorname{mex}(0, 1, 0, 1) = 2 $ and $ \operatorname{mex}(1, 2) = 0 $ . In the fourth test case, Evirir can choose $ b $ to be the entire array $ a $ , changing $ a $ from $ [\underline{3, 1, 4, 1, 5}] $ to $ [0] $ .