Informatica Online Judge

  책장정리 [1359 / 054F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 26   Total Tried : 157


The Champion of this Problem (C++) : gs15120 - 0ms / 1482byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 책장에 책을 쌓아서 보관한다.

책장에 모두 n권의 책이 쌓여 있으며, 각 책의 번호는 1번으로부터 n번까지의 번호가 있다.

이 문제의 목적은 위로부터 1번으로부터 n번까지의 순서로 책을 정리하는 것이다.

이 책장은 특징은 임의의 위치에서 책을 빼는 건 쉬우나 끼울 수가 없어서 정리할 때에는 항상 원하는 장소에서 책을 빼서, 가장 위에 올리는 식으로 정리를 해야한다.

모든 책을 정리하는데 옮기는 책의 수를 최소화하는 것이 목적이다.

예를 들어 책이 위로부터 4 1 2 3으로 쌓여 있다면, 가장 바닥에 있는 3을 위로 올린다.

3 4 1 2

다음으로 바닥의 2를 가장 위로 옮긴다.

2 3 4 1

마지막으로 1을 가장 위로 올린다.

1 2 3 4

따라서 3권을 옮기면 모두 정리할 수 있다. 다른 방법도 있지만 3권 이하로 옮길 수 있는 방법은 없다.

Input

이 문제는 ICPC형태로 여러 개의 테스트 케이스가 입력된다.

첫 번째 줄에 테스트 케이스의 수 T가 입력된다.

다음 줄부터 T개의 테스트 케이스가 다음과 같이 입력된다.

각 테스트 케이스의 첫 줄에는 자료의 수를 나타내는 정수 n이 입력된다.

다음 줄에는 n개의 원소가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= T <= 100
1 <= n < 20

Output

각 테스트 케이스별로 1줄에 하나씩 최소 옮기는 책의 횟수를 출력한다.

IO Example

입력
2
4
4 1 2 3
5
1 2 3 4 5

출력
3
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]