1712C.md (1489B)
1 Source: https://codeforces.com/problemset/problem/1712/C 2 3 C. Sort Zero 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 An array is sorted if it has no inversions 22 23 A Young Boy 24 25 You are given an array of $n$ positive integers $a_1,a_2,\ldots,a_n$. 26 27 In one operation you do the following: 28 29 1. Choose any integer $x$. 30 2. For all $i$ such that $a_i = x$, do $a_i := 0$ (assign $0$ to $a_i$). 31 32 Find the minimum number of operations required to sort the array in non-decreasing order. 33 34 Input 35 36 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. 37 38 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$). 39 40 The second line of each test case contains $n$ positive integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$). 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 43 44 Output 45 46 For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order. 47 48 Example 49 50 Input 51 52 ``` 53 5 54 55 3 56 57 3 3 2 58 59 4 60 61 1 3 1 3 62 63 5 64 65 4 1 5 3 2 66 67 4 68 69 2 4 1 2 70 71 1 72 73 1 74 ``` 75 76 Output 77 78 ``` 79 1 80 2 81 4 82 3 83 0 84 ``` 85 86 Note 87 88 In the first test case, you can choose $x = 3$ for the operation, the resulting array is $[0, 0, 2]$. 89 90 In the second test case, you can choose $x = 1$ for the first operation and $x = 3$ for the second operation, the resulting array is $[0, 0, 0, 0]$.