codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.