CF2085B Serval and Final MEX

You are given an array $ a $ consisting of $ n\ge 4 $ non-negative integers. You need to perform the following operation on $ a $ until its length becomes $ 1 $ : - Select two indices $ l $ and $ r $ ( $ 1\le {\color{red}{ l < r }} \le |a| $ ), and replace the subarray $ [a_l,a_{l+1},\ldots,a_r] $ with a single integer $ \operatorname{mex}([a_l,a_{l+1},\ldots,a_r]) $ , where $ \operatorname{mex}(b) $ denotes the minimum excluded (MEX) $ ^{\text{∗}} $ of the integers in $ b $ . In other words, let $ x=\operatorname{mex}([a_l,a_{l+1},\ldots,a_r]) $ , the array $ a $ will become $ [a_1,a_2,\ldots,a_{l-1},x,a_{r+1},a_{r+2},\ldots,a_{|a|}] $ . Note that the length of $ a $ decreases by $ (r-l) $ after this operation. Serval wants the final element in $ a $ to be $ 0 $ . Help him! More formally, you have to find a sequence of operations, such that after performing these operations in order, the length of $ a $ becomes $ 1 $ , and the final element in $ a $ is $ 0 $ . It can be shown that at least one valid operation sequence exists under the constraints of the problem, and the length of any valid operation sequence does not exceed $ n $ . Note that you do not need to minimize the number of operations. $ ^{\text{∗}} $ The minimum excluded (MEX) of a collection of integers $ b_1, b_2, \ldots, b_k $ is defined as the smallest non-negative integer $ x $ which does not occur in the collection $ b $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 4\le n\le 5000 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0\le a_i\le n $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

For each test case, output a single integer $ k $ ( $ 0\le k\le n $ ) in the first line of output — the length of the operation sequence. Then, output $ k $ lines, the $ i $ -th line containing two integers $ l_i $ and $ r_i $ ( $ 1\le l_i

In the first test case, since $ \operatorname{mex}([1,2,3,4])=0 $ , after the only operation, the array becomes $ [0] $ . In the second test case, the array $ a $ changes as follows: $ $$$ [\underline{0,1},0,0,1]\to [\underline{2,0},0,1]\to [\underline{1,0},1]\to [\underline{2,1}]\to [0]. $ $

In the third test case, the array $ a $ changes as follows: $ $ [0,0,0,0,\underline{0,0}]\to [0,0,\underline{0,0},1]\to [\underline{0,0},1,1]\to [\underline{1,1,1}]\to [0]. $ $$$