시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 0 0 0.000%

문제

큐 Q, 스택 A, 스택 B와 다음과 같은 연산이 있다.

QA(n): Q에서 수 하나를 빼고, A에 넣는다. 이 작업을 n번 반복한다.

QB(n): Q에서 수 하나를 빼고, B에 넣는다. 이 작업을 n번 반복한다.

QQ(n): Q에서 수 하나를 빼고, Q에 넣는다. 이 작업을 n번 반복한다.

AQ(n): A에서 수 하나를 빼고, Q에 넣는다. 이 작업을 n번 반복한다.

BQ(n): B에서 수 하나를 빼고, Q에 넣는다. 이 작업을 n번 반복한다.

AB(n): A에서 수 하나를 빼고, B에 넣는다. 이 작업을 n번 반복한다.

BA(n): B에서 수 하나를 빼고, A에 넣는다. 이 작업을 n번 반복한다.

위의 연산은 n의 값에 상관없이 모두 각각 한 번으로 친다.

처음에 큐에 수가 이미 채워져 있고, 두 스택은 비어있다. 이때, 큐에 수를 오름차순으로 만들때 필요한 연산의 최솟값은 몇 번일까?

예를 들어, 큐에 수가 (4 3 1 2 0)과 같이 채워져 있다고 하자. 이때, 큐는 다음과 같이 3번만에 정렬할 수 있다. QA(2), QQ(2), AQ(2) 

또, (5 4 1 3 2 0)과 같이 채워져 있다면, 4번만에 정렬할 수 있다. QB(2), QQ(1), QB(2), BQ(4)

큐에 들어있는 수를 정렬하기 위해 필요한 연산의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 큐에 들어있는 수의 개수 N이다. 다음 N개의 수는 큐에 들어있는 수가 앞에서부터 순서대로 주어진다. 큐에 들어있는 수는 모두 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 또, 한 숫자는 한 번씩만 주어진다. N은 10을 넘지 않는다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 큐를 정렬하는데 필요한 연산의 최솟값을 출력한다.

예제 입력 1

5 4 3 1 2 0
6 5 4 1 3 2 0
0

예제 출력 1

3
4
W3sicHJvYmxlbV9pZCI6IjQ5MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNTAgXHVjMThjXHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQwNTAgUSwgXHVjMmE0XHVkMGRkIEEsIFx1YzJhNFx1ZDBkZCBCXHVjNjQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNWYwXHVjMGIwXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PHN0cm9uZz5RQShuKTxcL3N0cm9uZz46IFFcdWM1ZDBcdWMxMWMgXHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJlN2NcdWFjZTAsIEFcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LiBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQ0IG5cdWJjODggXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDxzdHJvbmc+UUIobik8XC9zdHJvbmc+OiBRXHVjNWQwXHVjMTFjIFx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHViZTdjXHVhY2UwLCBCXHVjNWQwIFx1YjEyM1x1YjI5NFx1YjJlNC4gXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBuXHViYzg4IFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ8c3Ryb25nPlFRKG4pPFwvc3Ryb25nPjogUVx1YzVkMFx1YzExYyBcdWMyMTggXHVkNTU4XHViMDk4XHViOTdjIFx1YmU3Y1x1YWNlMCwgUVx1YzVkMCBcdWIxMjNcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgblx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0PHN0cm9uZz5BUShuKTxcL3N0cm9uZz46IEFcdWM1ZDBcdWMxMWMgXHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJlN2NcdWFjZTAsIFFcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LiBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQ0IG5cdWJjODggXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPlxyXG5cdDxzdHJvbmc+QlEobik8XC9zdHJvbmc+OiBCXHVjNWQwXHVjMTFjIFx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHViZTdjXHVhY2UwLCBRXHVjNWQwIFx1YjEyM1x1YjI5NFx1YjJlNC4gXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBuXHViYzg4IFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ8c3Ryb25nPkFCKG4pPFwvc3Ryb25nPjogQVx1YzVkMFx1YzExYyBcdWMyMTggXHVkNTU4XHViMDk4XHViOTdjIFx1YmU3Y1x1YWNlMCwgQlx1YzVkMCBcdWIxMjNcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgblx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0PHN0cm9uZz5CQShuKTxcL3N0cm9uZz46IEJcdWM1ZDBcdWMxMWMgXHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJlN2NcdWFjZTAsIEFcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LiBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQ0IG5cdWJjODggXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3MDRcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzQwIG5cdWM3NTggXHVhYzEyXHVjNWQwIFx1YzBjMVx1YWQwMFx1YzVjNlx1Yzc3NCBcdWJhYThcdWI0NTAgXHVhYzAxXHVhYzAxIFx1ZDU1YyBcdWJjODhcdWM3M2NcdWI4NWMgXHVjZTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjOThcdWM3NGNcdWM1ZDAgXHVkMDUwXHVjNWQwIFx1YzIxOFx1YWMwMCBcdWM3NzRcdWJiZjggXHVjYzQ0XHVjNmNjXHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViNDUwIFx1YzJhNFx1ZDBkZFx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkMDUwXHVjNWQwIFx1YzIxOFx1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQwIFx1YmE4NyBcdWJjODhcdWM3N2NcdWFlNGM/PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDA1MFx1YzVkMCBcdWMyMThcdWFjMDAgKDQgMyAxIDIgMClcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGMsIFx1ZDA1MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IDNcdWJjODhcdWI5Y2NcdWM1ZDAgXHVjODE1XHViODJjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFFBKDIpLCBRUSgyKSwgQVEoMikmbmJzcDs8XC9wPlxyXG48cD5cclxuXHRcdWI2MTAsICg1IDQgMSAzIDIgMClcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Y2M0NFx1YzZjY1x1YzgzOCBcdWM3ODhcdWIyZTRcdWJhNzQsIDRcdWJjODhcdWI5Y2NcdWM1ZDAgXHVjODE1XHViODJjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFFCKDIpLCBRUSgxKSwgUUIoMiksIEJRKDQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDA1MFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHViOTdjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkMDUwXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWQwNTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMDUwXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWIyOTQgXHViYWE4XHViNDUwIDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgTi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YzUyOVx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMTBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkMDUwXHViOTdjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDkzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNvcnQgdGhhdCBRdWV1ZSIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBxdWV1ZSBRLCBhIHN0YWNrIEEsIGFuZCBhIHN0YWNrIEIsIGFuZCB0aGUgZm9sbG93aW5nIG9wZXJhdGlvbnM6PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+UUEobik8XC9zdHJvbmc+OiBkZXF1ZXVlIGFuIGl0ZW0gZnJvbSBRLCBwdXNoaW5nIGl0IG9uIEE7IHJlcGVhdCBuIHRpbWVzPGJyIFwvPlxyXG48c3Ryb25nPlFCKG4pPFwvc3Ryb25nPjogZGVxdWV1ZSBhbiBpdGVtIGZyb20gUSwgcHVzaGluZyBpdCBvbiBCOyByZXBlYXQgbiB0aW1lczxiciBcLz5cclxuPHN0cm9uZz5RUShuKTxcL3N0cm9uZz46IGRlcXVldWUgYW4gaXRlbSBmcm9tIFEsIGVucXVldWUgaXQgYWdhaW4gaW4gUTsgcmVwZWF0IG4gdGltZXM8YnIgXC8+XHJcbjxzdHJvbmc+QVEobik8XC9zdHJvbmc+OiBwb3AgYW4gaXRlbSBmcm9tIEEsIGVucXVldWUgaXQgaW4gUTsgcmVwZWF0IG4gdGltZXM8YnIgXC8+XHJcbjxzdHJvbmc+QlEobik8XC9zdHJvbmc+OiBwb3AgYW4gaXRlbSBmcm9tIEIsIGVucXVldWUgaXQgaW4gUTsgcmVwZWF0IG4gdGltZXM8YnIgXC8+XHJcbjxzdHJvbmc+QUIobik8XC9zdHJvbmc+OiBwb3AgYW4gaXRlbSBmcm9tIEEsIHB1c2ggaXQgb24gQjsgcmVwZWF0IG4gdGltZXM8YnIgXC8+XHJcbjxzdHJvbmc+QkEobik8XC9zdHJvbmc+OiBwb3AgYW4gaXRlbSBmcm9tIEIsIHB1c2ggaXQgb24gQTsgcmVwZWF0IG4gdGltZXMuPFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCBlYWNoIG9mIHRoZSBhYm92ZSBpcyBjb25zaWRlcmVkIGEgc2luZ2xlIG9wZXJhdGlvbiwgcmVnYXJkbGVzcyBvZiB0aGUgdmFsdWUgb2Ygbi48XC9wPlxyXG5cclxuPHA+Tm93IGFzc3VtZSB0aGF0IHRoZSBxdWV1ZSBpcyBhbHJlYWR5IHBvcHVsYXRlZCB3aXRoIG51bWJlcnMgYW5kIHRoYXQgYm90aCBzdGFja3MgYXJlIGVtcHR5LCB3aGF0IGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIG5lZWRlZCB0byBoYXZlIHRoZSBzYW1lIG51bWJlcnMgaW4gdGhlIHF1ZXVlIGJ1dCBzb3J0ZWQgaW4gYW4gYXNjZW5kaW5nIG9yZGVyPyAoc21hbGxlc3QgaW4gZnJvbnQuKTxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIHF1ZXVlICg0IDMgMSAyIDApIHdoZXJlIDQgaXMgYXQgdGhlIGZyb250LCBjYW4gYmUgc29ydGVkIGluIHRocmVlIHN0ZXBzIGFzIGZvbGxvd3M6IFFBKDIpLCBRUSgyKSwgdGhlbiBBUSgyKS4gVGhlIHF1ZXVlICg1IDQgMSAzIDIgMCkgY2FuIGJlIHNvcnRlZCBpbiBmb3VyIG9wZXJhdGlvbnMgYXMgZm9sbG93czogUUIoMiksIFFRKDEpLCBRQigyKSwgQlEoNCkuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9wZXJhdGlvbnMgbmVlZGVkIHRvIHNvcnQgYSBnaXZlbiBxdWV1ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBhIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBzcGVjaVx1ZmIwMWVkIG9uIGEgc2luZ2xlIGxpbmUuIEVhY2ggdGVzdCBjYXNlIGlzIG1hZGUgb2YgTiArIDEgaW50ZWdlcnMuIFRoZSBcdWZiMDFyc3QgaW50ZWdlciBzcGVjaVx1ZmIwMWVzIE4gd2hpY2ggaXMgdGhlIG51bWJlciBvZiBlbGVtZW50cyBpbiB0aGUgcXVldWUuIEEgcXVldWUgb2YgTiBlbGVtZW50cyB3aWxsIGhhdmUgaW4gaXQgdGhlIGludGVnZXJzIGZyb20gMCB0byBOICZtaW51czsgMSBpbiBzb21lIHJhbmRvbSBvcmRlci4gVGhlIGludGVnZXJzIGluIHRoZSBxdWV1ZSBhcmUgc3BlY2lcdWZiMDFlZCBmcm9tIHRoZSBmcm9udCBvZiB0aGUgcXVldWUgdG8gdGhlIGJhY2suIE5vIHF1ZXVlIHdpbGwgaGF2ZSBtb3JlIHRoYW4gMTAgZWxlbWVudHMuPFwvcD5cclxuXHJcbjxwPlRoZSBlbmQgb2YgdGhlIHRlc3QgY2FzZXMgaXMgaWRlbnRpXHVmYjAxZWQgd2l0aCBhbiBpbnB1dCBsaW5lIHRoYXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOID0gMCAod2hpY2ggaXMgbm90IHBhcnQgb2YgdGhlIHRlc3QgY2FzZXMuKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgd3JpdGUgdGhlIHJlc3VsdCBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d