codeforces#P2200B. Deletion Sort
-
ID: 42024
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Deletion Sort
Problem Description
AksLolCoding is playing a game on an array $a$ of $n$ positive integers. During each turn:
- If $a$ is non-decreasing$^{\text{∗}}$, the game ends.
- Otherwise, AksLolCoding can choose any single element and remove it from the array.
Determine the minimum possible number of elements that can be remaining in the array after the game ends.
$^{\text{∗}}$$a$ is non-decreasing if $a_i\leq a_{i+1}$ for all $1\leq i\leq m-1$, where $m$ is the length of $a$.
The first line contains an integer $t$ ($1 \leq t \leq 1000$), the number of test cases.
The first line of each test case contains an integer $n$ ($1 \leq n \leq 10$).
The second line of each test case contains $n$ integers, the elements of $a$ ($1 \leq a_i \leq 100$).
For each test case, output an integer: the minimum possible number of elements left once the array is sorted.
Input Format
The first line contains an integer $t$ ($1 \leq t \leq 1000$), the number of test cases.
The first line of each test case contains an integer $n$ ($1 \leq n \leq 10$).
The second line of each test case contains $n$ integers, the elements of $a$ ($1 \leq a_i \leq 100$).
Output Format
For each test case, output an integer: the minimum possible number of elements left once the array is sorted.
3
4
1 4 2 3
1
100
2
6 7
,
1
1
2
Hint
In the first test case, the minimum of $1$ element can be achieved by removing $1$, $2$, and $3$ in that order.
In the second and third test cases, no elements can be removed.