AT_arc195_d [ARC195D] Swap and Erase

There is a sequence $ A = (A_1,\ldots,A_N) $ . You can perform the following two types of operations any number of times in any order: - Let $ K $ be the length of $ A $ just before the operation. Choose an integer $ i $ such that $ 1 \leq i \leq K-1 $ , and swap the $ i $ -th and $ (i+1) $ -th elements of $ A $ . - Let $ K $ be the length of $ A $ just before the operation. Choose an integer $ i $ such that $ 1 \leq i \leq K $ and all the values from the $ 1 $ -st through the $ i $ -th elements of $ A $ are equal, and delete all the elements from the $ 1 $ -st through the $ i $ -th of $ A $ . Find the minimum total number of operations required to make $ A $ an empty sequence. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Print the answer for each test case in order, separated by newlines.

### Sample Explanation 1 For the 1st test case, $ A $ can be made empty by the following three operations: - Swap the 3rd and 4th elements of $ A $ . Now, $ A $ is $ (1,1,1,2,2) $ . - Delete the 1st through 3rd elements of $ A $ . Now, $ A $ is $ (2,2) $ . - Delete the 1st through 2nd elements of $ A $ . Now, $ A $ is an empty sequence. For the 2nd test case, $ A $ can be made empty by deleting the 1st element four times. Also, it is impossible to make $ A $ empty in three or fewer operations. ### Constraints - $ 1\leq T\leq 10^5 $ - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq N $ - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ . - All input values are integers.