책 쌓기

시간 제한1초메모리 제한128 MB

요약

책 크기 배열이 주어질 때, 위쪽 부분이 비감소일 때만 책 하나를 꺼내 맨 위로 올리는 연산으로 정렬하는 최소 횟수를 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

선영이는 다양한 크기의 책을 하나의 스택으로 쌓아 보관한다. 스택을 가장 위에서부터 아래로 내려가며 볼 때 책의 크기가 한 번도 줄어들지 않으면(즉, 위에서 아래로 크기가 감소하지 않는 순서로 놓여 있으면) 그 스택은 안정된 상태라고 한다. 안정된 상태가 아니면 스택이 무너질 수 있다.

선영이는 스택이 무너지지 않도록 책을 크기 순으로 정렬하려고 한다. 한 번의 작업에서 선영이는 스택의 중간이나 맨 아래에 있는 책 하나를 뽑아 스택의 가장 위에 올려놓는다. 단, 뽑으려는 책보다 위에 쌓여 있는 부분은 그 순간에 반드시 안정된 상태여야 한다.

예를 들어 위에서부터 $3, 4, 1, 2$ 의 순서로 쌓인 스택은 세 번의 작업으로 크기 순(위에서부터 $1, 2, 3, 4$ )으로 정렬할 수 있으며, 이때 필요한 작업 수의 최솟값은 $3$ 이다.

현재 쌓여 있는 책의 상태가 주어졌을 때, 스택을 안정된 상태로 만들기 위해 필요한 작업 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. ( $T \le 100$ )

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 책의 수 $n$ 이 주어지고 ( $1 \le n \le 50$ ), 둘째 줄에는 스택의 가장 위에서부터 순서대로 책의 크기 $s_i$ 가 주어진다. ( $1 \le s_i \le 1000$ )

출력

각 테스트 케이스마다 스택을 안정된 상태로 만들기 위해 필요한 작업 수의 최솟값을 한 줄에 하나씩 출력한다.

예제2

예제 1

입력

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

예상 출력

예제 2
입력
```
1
3
3 1 2
```
예상 출력
```
3
```