시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 197 46 38 40.000%

문제

선영이는 다양한 크기의 책을 쌓아서 스택 형태로 보관한다. 이런 스택의 가장 위에서부터 크기가 감소하지 않는 순서로 책이 쌓여져 있다면, 스택이 안정된 상태라고 한다. 그렇지 않은 경우에는 스택이 무너질 수도 있다.

선영이는 책이 무너지는 것을 막기 위해서 크기 순으로 스택을 정렬하려고 한다. 선영이는 스택의 중간 (또는 바닥)에서 책을 하나 뺀 다음, 가장 위에 놓는다. 하지만, 빼려고 하는 책의 위에 있는 스택이 안정된 상태이어야 한다.

아래 그림은 3, 4, 1, 2로 쌓여진 책을 크기 순으로 정렬하는 방법이다.

현재 책이 쌓여져 있는 상태가 입력으로 주어졌을 때, 안정된 상태로 책을 쌓기 위해 최소 몇 단계가 필요한지 구하는 프로그램을 작성하시오. 위의 그림의 경우에 답은 3이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100보다 작거나 같다.

각 테스트 케이스의 첫째 줄에는 책의 수 n이 주어진다. (1 ≤ n ≤ 50) 다음 줄에는 책의 크기 si가 스택의 맨 위에서부터 순서대로 주어진다. (1 ≤ si ≤ 1000)

출력

각 테스트 케이스에 대해서, 필요한 단계의 수의 최소값을 출력한다.

예제 입력 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

예제 출력 1

3
53
0
1234567
W3sicHJvYmxlbV9pZCI6IjU0MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjNDUgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViMmU0XHVjNTkxXHVkNTVjIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjNDVcdWM3NDQgXHVjMzEzXHVjNTQ0XHVjMTFjIFx1YzJhNFx1ZDBkZCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViY2Y0XHVhZDAwXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVjMmE0XHVkMGRkXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3MDRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1Y2M0NVx1Yzc3NCBcdWMzMTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0XHViYTc0LCBcdWMyYTRcdWQwZGRcdWM3NzQgXHVjNTQ4XHVjODE1XHViNDFjIFx1YzBjMVx1ZDBkY1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzJhNFx1ZDBkZFx1Yzc3NCBcdWJiMzRcdWIxMDhcdWM5YzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1Y2M0NVx1Yzc3NCBcdWJiMzRcdWIxMDhcdWM5YzBcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMDZjXHVhZTMwIFx1YzIxY1x1YzczY1x1Yjg1YyBcdWMyYTRcdWQwZGRcdWM3NDQgXHVjODE1XHViODJjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWM5MTFcdWFjMDQgKFx1YjYxMFx1YjI5NCBcdWJjMTRcdWIyZTUpXHVjNWQwXHVjMTFjIFx1Y2M0NVx1Yzc0NCBcdWQ1NThcdWIwOTggXHViZTgwIFx1YjJlNFx1Yzc0YywgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViZTdjXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWNjNDVcdWM3NTggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWQwZGRcdWM3NzQgXHVjNTQ4XHVjODE1XHViNDFjIFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgMywgNCwgMSwgMlx1Yjg1YyBcdWMzMTNcdWM1ZWNcdWM5YzQgXHVjYzQ1XHVjNzQ0IFx1ZDA2Y1x1YWUzMCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVjODE1XHViODJjXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdGFja2Jvb2sucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTUzcHg7IHdpZHRoOjU3MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWNjNDVcdWM3NzQgXHVjMzEzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzU0OFx1YzgxNVx1YjQxYyBcdWMwYzFcdWQwZGNcdWI4NWMgXHVjYzQ1XHVjNzQ0IFx1YzMxM1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjZDVjXHVjMThjJm5ic3A7XHViYTg3IFx1YjJlOFx1YWNjNFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NWNcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjJmNVx1Yzc0MCAzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViMjk0IDEwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M0NVx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDUwKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M0NVx1Yzc1OCBcdWQwNmNcdWFlMzAgczxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjMmE0XHVkMGRkXHVjNzU4IFx1YjllOCBcdWM3MDRcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBzPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMmU4XHVhY2M0XHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU0MzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKb2huXHUyMDE5cyBCb29rIFN0YWNrIiwiZGVzY3JpcHRpb24iOiI8cD5Kb2huIGhhcyBhIGJpZyBzdGFjayBvZiBib29rcyBvZiB2YXJpb3VzIHNpemVzLiBTdWNoIGEgc3RhY2sgaXMgc3RhYmxlIGlmIHRoZSBib29rcyBoYXZlIG5vbmRlY3JlYXNpbmcgc2l6ZXMgKHZpZXdlZCBmcm9tIHRvcCB0byBib3R0b20pOyBvdGhlcndpc2UsIGl0IGlzIHVuc3RhYmxlLCBhbmQgbGlrZWx5IHRvIGZhbGwgb3Zlci48XC9wPlxyXG5cclxuPHA+VG8gcHJldmVudCB0aGlzLCBKb2huIHdhbnRzIHRvIHNvcnQgdGhlIGJvb2tzIGluIHRoZSBzdGFjayBieSBzaXplLiBIZSBkb2VzIHNvIGJ5IHB1bGxpbmcgb3V0IGEgYm9vayBmcm9tIHNvbWV3aGVyZSBpbiB0aGUgbWlkZGxlIChvciBib3R0b20pIG9mIHRoZSBzdGFjayBhbmQgdGhlbiBwdXR0aW5nIGl0IGJhY2sgb24gdG9wLiBIb3dldmVyLCBoZSBjYW4gb25seSBwdWxsIG91dCBhIGJvb2sgc2FmZWx5IGlmIHRoZSBib29rcyBvbiB0b3Agb2YgaXQgYWxyZWFkeSBmb3JtIGEgc3RhYmxlIHN0YWNrLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgSm9obiBoYXMgYSBzdGFjayBvZiBmb3VyIGJvb2tzIHdpdGggc2l6ZXMgMywgNCwgMSBhbmQgMiAoZnJvbSB0b3AgdG8gYm90dG9tKSB0aGVuIGhlIGNhbiBzb3J0IHRoZW0gYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdGFja2Jvb2sucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTUzcHg7IHdpZHRoOjU3MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBkZXRlcm1pbmUgaG93IG1hbnkgc3RlcHMgYXJlIHJlcXVpcmVkIHRvIHNvcnQgYSBnaXZlbiBzdGFjayBvZiBib29rcy4gSW4gdGhlIGV4YW1wbGUgYWJvdmUsIHdoaWNoIGNvcnJlc3BvbmRzIHRvIHRoZSBcdWZiMDFyc3Qgc2FtcGxlIGNhc2UsIHRoZSBhbnN3ZXIgaXMgMy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgNTApOiB0aGUgbnVtYmVyIG9mIGJvb2tzLjxcL2xpPlxyXG5cdDxsaT5vbmUgbGluZSBjb250YWluaW5nIG4gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHM8c3ViPmk8XC9zdWI+ICgxICZsZTsgczxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCBmb3IgMSAmbGU7IGkgJmxlOyBuKTogdGhlIHNpemVzIG9mIHRoZSBib29rcywgYXMgdGhleSBhcHBlYXIgaW4gdGhlIGluaXRpYWwgc3RhY2sgZnJvbSB0b3AgdG8gYm90dG9tLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyByZXF1aXJlZCB0byBzb3J0IHRoZSBzdGFjayB1c2luZyB0aGUgYWxnb3JpdGhtIGRlc2NyaWJlZCBhYm92ZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==