CF2165D Path Split

You are given a sequence of $ n $ integers $ a_1,a_2,\ldots,a_n $ . You would like to partition $ a $ into several subsequences $ ^{\text{∗}} $ $ b_1,b_2,\ldots,b_k $ , satisfying the following conditions: - Each element in $ a $ belongs to exactly one of $ b_i $ . - For each sequence $ b_i $ , let its elements be $ b_{i,1},b_{i,2},\ldots,b_{i,p_i} $ . For every $ 1\le j

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

For each test case, print a single integer on one line — the minimum number of subsequences $ a $ can be partitioned into.

In the first test case, we can partition $ a $ into subsequences $ [1] $ . It is obvious that we cannot partition $ a $ into fewer subsequences; thus, $ 1 $ is the answer. In the third test case, we can partition $ a $ into subsequences $ [11,10,11,10],[13],[11],[11],[13] $ . Please note that $ [11,10,11,11,11,10] $ is not a valid sequence, since $ |11-11|=0\neq1 $ .