시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB32301309105042.493%

문제

상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다.

오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다.

책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 수 있다. 가장 먼저, 2번 책을 뺀 다음에 가장 위에 놓는다. 그렇게 되면 (2, 3, 1)이 된다. 마지막으로, 1을 뺀 다음 가장 위에 놓으면 (1, 2, 3)이 된다.

현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 책의 개수 N이 주어진다. (N ≤ 300,000)

다음 N개 줄에는 가장 위에 있는 책부터 아래에 있는 책까지 순서대로 주어진다.

출력

첫째 줄에 몇 번만에 책을 정렬할 수 있는지 출력한다.

예제 입력 1

3
3
2
1

예제 출력 1

2

예제 입력 2

4
1
3
4
2

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjI4NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YjBcdWI5YWNcdWM5ZDFcdWM1ZDQgXHViM2M0XHVjMTFjXHVhZDAwXHVjNzc0IFx1Yzc4OFx1YzViNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWFjZjVcdWQ1NTlcdWM3NTggXHVjNzdjXHVjNzc4XHVjNzkwXHVhYzAwIFx1YjQxOFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjYzQ1XHVjNzQ0IFx1YjllNFx1YzZiMCBcdWI5Y2VcdWM3NzQgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzlkMVx1YzVkMCBcdWNjNDVcdWM3YTVcdWM3NzQgXHVjNWM2XHVjNWI0XHVjMTFjIFx1Y2M0NVx1Yzc0NCBcdWQwZDFcdWNjOThcdWI3ZmMgXHVjMzEzXHVjNTQ0XHViMTkzXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwIFx1YzYyNFx1Yjc5Y1x1YjljY1x1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOWQxXHVjNWQwXHVjMTFjIFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWNkZThcdWQ1NThcdWIyOTQgXHViMGEwXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjYzQ1XHVjNzQ0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODE1XHViODJjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IFx1Y2M0NVx1Yzc0MCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YjRhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjYzQ1XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWJjMTFcdWM1ZDAgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjYzQ1XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1Y2M0NSBcdWQ1NThcdWIwOThcdWI5N2MgXHViZTgwIFx1YjJlNFx1Yzc0YywgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjNDVcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWNjNDUgXHVjNzc0XHViOTg0XHVjNzU4IFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gMVx1Yzc0MCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWMxMWNcdWIyOTQgXHVjYzQ1XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzcwNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWNjNDVcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Yzc3ZFx1YzczY1x1YmE3NCAoMSwgMiwgLi4uLCBOKVx1Yzc3NCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWNjNDVcdWM3NzQgM1x1YWQ4Y1x1Yzc4OFx1YWNlMCBcdWNjOThcdWM3NGNcdWM1ZDAgKDMsIDIsIDEpXHViODVjIFx1YzMxM1x1YzVlY1x1Yzc4OFx1Yzc0NCBcdWI1NGMsIDJcdWJjODggXHViOWNjXHVjNWQwIFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNjNDVcdWM3NDQgXHVjMzEzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWJhM2NcdWM4MDAsIDJcdWJjODggXHVjYzQ1XHVjNzQ0IFx1YmU4MCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWI0MThcdWJhNzQgKDIsIDMsIDEpXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCAxXHVjNzQ0IFx1YmU4MCBcdWIyZTRcdWM3NGMgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM3M2NcdWJhNzQgKDEsIDIsIDMpXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjN2FjIFx1Y2M0NVx1Yzc3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjMzEzXHVjNWVjXHVjNzg4XHViMjk0XHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmE4NyBcdWJjODhcdWI5Y2NcdWM1ZDAgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWMzMTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzQ1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjYzQ1XHViZDgwXHVkMTMwIFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjYzQ1XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhODcgXHViYzg4XHViOWNjXHVjNWQwIFx1Y2M0NVx1Yzc0NCBcdWM4MTVcdWI4MmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjg3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktOSklHRSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGEgaG9tZSBsaWJyYXJ5IGNvbnNpc3Rpbmcgb2YgTiBib29rcyBhcnJhbmdlZCBvbmUgb24gdG9wIG9mIHRoZSBvdGhlciBpbiBhIG5hcnJvdyBjYWJpbmV0LiBTaW5jZSBiZWluZyB3ZWxsIHRyYWluZWQgaW4gdGhlIHNlY3JldHMgb2YgYWxwaGFiZXQgaW4gdGhlIHByZXZpb3VzIHRhc2ssIGhlIG5vdyB3aXNoZXMgdG8gYXJyYW5nZSB0aGUgYm9va3MgYWxwaGFiZXRpY2FsbHksIHNvIHRoYXQgdGhlIGJvb2sgd2hvc2UgdGl0bGUgY29tZXMgZmlyc3QgYWxwaGFiZXRpY2FsbHkgZW5kcyB1cCBvbiB0b3AsIGFuZCB0aGUgYWxwaGFiZXRpY2FsbHkgbGFzdCBvbmUgYXQgdGhlIGJvdHRvbSBvZiB0aGUgcGlsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gY2FuIGVhc2lseSBwdWxsIGEgYm9vayBvdXQgb2YgdGhlIGNhYmluZXQsIGJ1dCBpdCBpcyBkaWZmaWN1bHQgdG8gcHVzaCBpdCBiYWNrIGludG8gdGhlIHBpbGUsIHNvIHRoZSBib29rIGNhbiBvbmx5IGJlIHJldHVybmVkIHRvIHRoZSB0b3Agb2YgdGhlIHBpbGUuIFRodXMsIHRoZSBvbmx5IGF2YWlsYWJsZSBtZXRob2Qgb2Ygc29ydGluZyB0aGUgYm9va3MgaXMgcmVwZWF0ZWRseSBwdWxsaW5nIGEgYm9vayBvdXQgb2YgdGhlIHBpbGUgYW5kIHBsYWNpbmcgaXQgb24gdG9wIG9mIHRoZSBwaWxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgYm9va3MgYXJlIGxhYmVsbGVkIHdpdGggaW50ZWdlcnMgZnJvbSAxIHRvIE4sIGluIGFscGhhYmV0aWNhbCBvcmRlci4gVGhlcmVmb3JlLCBNaXJrbyB3YW50cyB0aGVtIHRvIGJlIG9yZGVyZWQgYXMgKDEsIDIsIC4uLiwgTiksIGNvdW50aW5nIGZyb20gdGhlIHRvcC4gRm9yIGV4YW1wbGUsIGlmIE4gPSAzIGFuZCB0aGUgc3RhcnRpbmcgb3JkZXIgaXMgKDMsIDIsIDEpLCB0d28gbW92ZXMgYXJlIHN1ZmZpY2llbnQuIEZpcnN0LCBoZSBwdWxscyBvdXQgdGhlIGJvb2sgbnVtYmVyIDIgYW5kIHBsYWNlcyBpdCBvbiB0b3AsIHNvIHRoZSBwaWxlIGJlY29tZXMgKDIsIDMsIDEpLiBBZnRlciB0aGF0LCBoZSBkb2VzIHRoZSBzYW1lIHdpdGggYm9vayBudW1iZXIgMSwgdGh1cyB0aGUgcGlsZSBiZWNvbWVzICgxLCAyLCAzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVscCBNaXJrbyBieSBjYWxjdWxhdGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgbmVlZGVkIHRvIHNvcnQgYSBnaXZlbiBzdGFydGluZyBvcmRlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKE4gJmxlOyAzMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIuIFRoZXNlIE4gaW50ZWdlcnMgcmVwcmVzZW50IHRoZSBvcmRlciBvZiBNaXJrbyZyc3F1bztzIGJvb2tzIGZyb20gdG9wIHRvIGJvdHRvbSBvZiB0aGUgY2FiaW5ldC4gRWFjaCBvZiB0aGUgaW50ZWdlcnMgMSwgMiwgLi4uLCBOIGFwcGVhcnMgZXhhY3RseSBvbmNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 4번