시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRcdWNjOThcdWM3NGNcdWM1ZDAgXHVkMDUwXHVjNWQwIFx1YzIxOFx1YWMwMCBcdWM3NzRcdWJiZjggXHVjYzQ0XHVjNmNjXHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViNDUwIFx1YzJhNFx1ZDBkZFx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1ZDA1MFx1YzVkMCBcdWMyMThcdWI5N2MgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0MCBcdWJhODcgXHViYzg4XHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwNTBcdWM1ZDAgXHVjMjE4XHVhYzAwICg0IDMgMSAyIDApXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWNjNDRcdWM2Y2NcdWM4MzggXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgXHVkMDUwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgM1x1YmM4OFx1YjljY1x1YzVkMCBcdWM4MTVcdWI4MmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gUUEoMiksIFFRKDIpLCBBUSgyKSZuYnNwOzxcL3A+XHJcbjxwPlxyXG5cdFx1YjYxMCwgKDUgNCAxIDMgMiAwKVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVjYzQ0XHVjNmNjXHVjODM4IFx1Yzc4OFx1YjJlNFx1YmE3NCwgNFx1YmM4OFx1YjljY1x1YzVkMCBcdWM4MTVcdWI4MmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gUUIoMiksIFFRKDEpLCBRQigyKSwgQlEoNCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMDUwXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjODE1XHViODJjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDA1MFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWIyOTQgXHVkMDUwXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjNTVlXHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDA1MFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIE4tMVx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWQ1NWMgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU1YyBcdWJjODhcdWM1MjlcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIDEwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDA1MFx1Yjk3YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5MzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTb3J0IHRoYXQgUXVldWUiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgcXVldWUgUSwgYSBzdGFjayBBLCBhbmQgYSBzdGFjayBCLCBhbmQgdGhlIGZvbGxvd2luZyBvcGVyYXRpb25zOjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlFBKG4pPFwvc3Ryb25nPjogZGVxdWV1ZSBhbiBpdGVtIGZyb20gUSwgcHVzaGluZyBpdCBvbiBBOyByZXBlYXQgbiB0aW1lczxiciBcLz5cclxuPHN0cm9uZz5RQihuKTxcL3N0cm9uZz46IGRlcXVldWUgYW4gaXRlbSBmcm9tIFEsIHB1c2hpbmcgaXQgb24gQjsgcmVwZWF0IG4gdGltZXM8YnIgXC8+XHJcbjxzdHJvbmc+UVEobik8XC9zdHJvbmc+OiBkZXF1ZXVlIGFuIGl0ZW0gZnJvbSBRLCBlbnF1ZXVlIGl0IGFnYWluIGluIFE7IHJlcGVhdCBuIHRpbWVzPGJyIFwvPlxyXG48c3Ryb25nPkFRKG4pPFwvc3Ryb25nPjogcG9wIGFuIGl0ZW0gZnJvbSBBLCBlbnF1ZXVlIGl0IGluIFE7IHJlcGVhdCBuIHRpbWVzPGJyIFwvPlxyXG48c3Ryb25nPkJRKG4pPFwvc3Ryb25nPjogcG9wIGFuIGl0ZW0gZnJvbSBCLCBlbnF1ZXVlIGl0IGluIFE7IHJlcGVhdCBuIHRpbWVzPGJyIFwvPlxyXG48c3Ryb25nPkFCKG4pPFwvc3Ryb25nPjogcG9wIGFuIGl0ZW0gZnJvbSBBLCBwdXNoIGl0IG9uIEI7IHJlcGVhdCBuIHRpbWVzPGJyIFwvPlxyXG48c3Ryb25nPkJBKG4pPFwvc3Ryb25nPjogcG9wIGFuIGl0ZW0gZnJvbSBCLCBwdXNoIGl0IG9uIEE7IHJlcGVhdCBuIHRpbWVzLjxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgZWFjaCBvZiB0aGUgYWJvdmUgaXMgY29uc2lkZXJlZCBhIHNpbmdsZSBvcGVyYXRpb24sIHJlZ2FyZGxlc3Mgb2YgdGhlIHZhbHVlIG9mIG4uPFwvcD5cclxuXHJcbjxwPk5vdyBhc3N1bWUgdGhhdCB0aGUgcXVldWUgaXMgYWxyZWFkeSBwb3B1bGF0ZWQgd2l0aCBudW1iZXJzIGFuZCB0aGF0IGJvdGggc3RhY2tzIGFyZSBlbXB0eSwgd2hhdCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyBuZWVkZWQgdG8gaGF2ZSB0aGUgc2FtZSBudW1iZXJzIGluIHRoZSBxdWV1ZSBidXQgc29ydGVkIGluIGFuIGFzY2VuZGluZyBvcmRlcj8gKHNtYWxsZXN0IGluIGZyb250Lik8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBxdWV1ZSAoNCAzIDEgMiAwKSB3aGVyZSA0IGlzIGF0IHRoZSBmcm9udCwgY2FuIGJlIHNvcnRlZCBpbiB0aHJlZSBzdGVwcyBhcyBmb2xsb3dzOiBRQSgyKSwgUVEoMiksIHRoZW4gQVEoMikuIFRoZSBxdWV1ZSAoNSA0IDEgMyAyIDApIGNhbiBiZSBzb3J0ZWQgaW4gZm91ciBvcGVyYXRpb25zIGFzIGZvbGxvd3M6IFFCKDIpLCBRUSgxKSwgUUIoMiksIEJRKDQpLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIG5lZWRlZCB0byBzb3J0IGEgZ2l2ZW4gcXVldWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gYSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgc3BlY2lcdWZiMDFlZCBvbiBhIHNpbmdsZSBsaW5lLiBFYWNoIHRlc3QgY2FzZSBpcyBtYWRlIG9mIE4gKyAxIGludGVnZXJzLiBUaGUgXHVmYjAxcnN0IGludGVnZXIgc3BlY2lcdWZiMDFlcyBOIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZWxlbWVudHMgaW4gdGhlIHF1ZXVlLiBBIHF1ZXVlIG9mIE4gZWxlbWVudHMgd2lsbCBoYXZlIGluIGl0IHRoZSBpbnRlZ2VycyBmcm9tIDAgdG8gTiAmbWludXM7IDEgaW4gc29tZSByYW5kb20gb3JkZXIuIFRoZSBpbnRlZ2VycyBpbiB0aGUgcXVldWUgYXJlIHNwZWNpXHVmYjAxZWQgZnJvbSB0aGUgZnJvbnQgb2YgdGhlIHF1ZXVlIHRvIHRoZSBiYWNrLiBObyBxdWV1ZSB3aWxsIGhhdmUgbW9yZSB0aGFuIDEwIGVsZW1lbnRzLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSB0ZXN0IGNhc2VzIGlzIGlkZW50aVx1ZmIwMWVkIHdpdGggYW4gaW5wdXQgbGluZSB0aGF0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiA9IDAgKHdoaWNoIGlzIG5vdCBwYXJ0IG9mIHRoZSB0ZXN0IGNhc2VzLik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIHRoZSByZXN1bHQgb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==