NIT Destroys the Universe

题意翻译

## 题目描述 定义 $\operatorname{mex}$ 为一个集合中最小的没有出现过的非负整数。 给定一个由 $n$ 个非负整数组成的的序列 $a$，NIT 可以进行若干次操作，每次操作选择 $l$ 和 $r$（$1\le l \le r \le n$），将 $a_l, a_{l+1} \cdots a_r$ 全部修改为 $\operatorname{mex}(\{a_l, a_{l+1} \cdots a_r\})$。本题有多组数据，对于每一组数据，请回答 NIT 最少需要多少次操作可以让整个序列都为 $0$。 ## 输入格式 第一行一个整数 $T$，表示有 $T$ 组询问。 对于每一组询问，第一行一个整数 $n$，表示序列长度，第二行 $n$ 个整数，表示这个序列。 ## 输出格式 共 $T$ 行，每行一个整数，表示对应一组询问的答案。 ## 样例解释 对于第一个测试样例，不要操作。 对于第二个测试样例，需要一次操作，选择 $l=2,r=5$。 对于第三个测试样例，需要两次操作，可以第一次选择 $l=4,r=4$，第二次选择 $l=2,r=6$。 对于第四个测试样例，需要一次操作，选择 $l=1,r=1$。 ## 数据范围 $1 \le t \le 10^4$，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。

题目描述

For a collection of integers $ S $ , define $ \operatorname{mex}(S) $ as the smallest non-negative integer that does not appear in $ S $ . NIT, the cleaver, decides to destroy the universe. He is not so powerful as Thanos, so he can only destroy the universe by snapping his fingers several times. The universe can be represented as a 1-indexed array $ a $ of length $ n $ . When NIT snaps his fingers, he does the following operation on the array: - He selects positive integers $ l $ and $ r $ such that $ 1\le l\le r\le n $ . Let $ w=\operatorname{mex}(\{a_l,a_{l+1},\dots,a_r\}) $ . Then, for all $ l\le i\le r $ , set $ a_i $ to $ w $ . We say the universe is destroyed if and only if for all $ 1\le i\le n $ , $ a_i=0 $ holds. Find the minimum number of times NIT needs to snap his fingers to destroy the universe. That is, find the minimum number of operations NIT needs to perform to make all elements in the array equal to $ 0 $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). Description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1\le n\le 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_n $ ( $ 0\le a_i\le 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print one integer — the answer to the problem.

输入输出样例

输入样例 #1

4
4
0 0 0 0
5
0 1 2 3 4
7
0 2 3 0 1 2 0
1
1000000000

输出样例 #1

0
1
2
1

说明

In the first test case, we do $ 0 $ operations and all elements in the array are already equal to $ 0 $ . In the second test case, one optimal way is doing the operation with $ l=2 $ , $ r=5 $ . In the third test case, one optimal way is doing the operation twice, respectively with $ l=4 $ , $ r=4 $ and $ l=2 $ , $ r=6 $ . In the fourth test case, one optimal way is doing the operation with $ l=1 $ , $ r=1 $ .

**题目大意：**
定义一个集合S的mex(S)为这个集合中最小的没有出现过的非负整数。

NIT可以通过多次操作来销毁宇宙。每次操作，他选择一个序列的连续子段，并将这个子段中的所有数修改为这个子段的mex值。现在，对于给定的多个序列，需要回答NIT至少需要多少次操作才能让整个序列都变为0。

**输入格式：**
第一行包含一个整数T，表示有T组询问。
每组询问包含两行，第一行一个整数n，表示序列长度，第二行n个整数，表示这个序列。

**输出格式：**
共T行，每行一个整数，表示对应一组询问的答案。

**样例解释：**
- 第一个测试样例不需要操作。
- 第二个测试样例需要一次操作，选择l=2,r=5。
- 第三个测试样例需要两次操作，可以第一次选择l=4,r=4，第二次选择l=2,r=6。
- 第四个测试样例需要一次操作，选择l=1,r=1。

**数据范围：**
$1 \le t \le 10^4$，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。**题目大意：** 定义一个集合S的mex(S)为这个集合中最小的没有出现过的非负整数。 NIT可以通过多次操作来销毁宇宙。每次操作，他选择一个序列的连续子段，并将这个子段中的所有数修改为这个子段的mex值。现在，对于给定的多个序列，需要回答NIT至少需要多少次操作才能让整个序列都变为0。 **输入格式：** 第一行包含一个整数T，表示有T组询问。 每组询问包含两行，第一行一个整数n，表示序列长度，第二行n个整数，表示这个序列。 **输出格式：** 共T行，每行一个整数，表示对应一组询问的答案。 **样例解释：** - 第一个测试样例不需要操作。 - 第二个测试样例需要一次操作，选择l=2,r=5。 - 第三个测试样例需要两次操作，可以第一次选择l=4,r=4，第二次选择l=2,r=6。 - 第四个测试样例需要一次操作，选择l=1,r=1。 **数据范围：** $1 \le t \le 10^4$，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。