Stacking Books

Time limit1sMemory limit128 MB

Summary

Given a stack of book sizes, find the fewest moves that pull one book to the top (only when the part above it is non-decreasing) to sort the stack.

Level: Medium4 of 10
Topics: Greedy, Sorting, Implementation, Brute force
Solved: No attempts yet

Problem

Sunyoung keeps books of various sizes stored as a single stack. Reading the stack from the top downward, if the sizes never decrease (that is, the books are arranged in non-decreasing order of size from top to bottom), the stack is said to be stable. Otherwise the stack may topple.

To keep the stack from toppling, Sunyoung wants to sort the books by size. In one operation she pulls a single book out of the middle or the very bottom of the stack and places it on top. However, at that moment the part of the stack lying above the book she removes must be stable.

For example, a stack piled as $3, 4, 1, 2$ from the top can be sorted by size ( $1, 2, 3, 4$ from the top) in three operations, and the minimum number of operations needed is $3$ .

Given the current arrangement of the books, write a program that finds the minimum number of operations required to make the stack stable.

Input

The first line contains the number of test cases $T$ . ( $T \le 100$ )

Each test case consists of two lines. The first line contains the number of books $n$ ( $1 \le n \le 50$ ), and the second line contains the sizes $s_i$ of the books in order from the top of the stack to the bottom. ( $1 \le s_i \le 1000$ )

Output

For each test case, print on its own line the minimum number of operations required to make the stack stable.

Examples2

Example 1

Input

4
4
3 4 1 2
8
3 1 4 1 5 9 2 6
5
1 42 42 42 1000
22
4 1 2 5 6 7 9 10 3 13 17 11 12 14 19 20 22 8 15 16 18 21

Expected output

Example 2
Input
```
1
3
3 1 2
```
Expected output
```
3
```