[Solution] Sort Zero Codeforces Solution

C. Sort Zero

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array of 

𝑛$n$ positive integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$.

In one operation you do the following:

1. Choose any integer 𝑥$x$.
2. For all 𝑖$i$ such that 𝑎𝑖=𝑥$a_i=x$, do 𝑎𝑖:=0$a_i:=0$ (assign 0$0$ to 𝑎𝑖$a_i$).

Find the minimum number of operations required to sort the array in non-decreasing order.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 Description of the test cases follows.

The first line of each test case contains a single integer 𝑛$n$ (1≤𝑛≤105$1\le n\le {10}^5$).

The second line of each test case contains 𝑛$n$ positive integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑛$1\le a_i\le n$).

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 105${10}^5$.

Output

For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.