시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 392 174 128 43.098%

문제

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

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

책은 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
W3sicHJvYmxlbV9pZCI6IjI4NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YjBcdWI5YWNcdWM5ZDFcdWM1ZDQgXHViM2M0XHVjMTFjXHVhZDAwXHVjNzc0IFx1Yzc4OFx1YzViNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWFjZjVcdWQ1NTlcdWM3NTggXHVjNzdjXHVjNzc4XHVjNzkwXHVhYzAwIFx1YjQxOFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjYzQ1XHVjNzQ0IFx1YjllNFx1YzZiMCBcdWI5Y2VcdWM3NzQgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzlkMVx1YzVkMCBcdWNjNDVcdWM3YTVcdWM3NzQgXHVjNWM2XHVjNWI0XHVjMTFjIFx1Y2M0NVx1Yzc0NCBcdWQwZDFcdWNjOThcdWI3ZmMgXHVjMzEzXHVjNTQ0XHViMTkzXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4XHVjNzQwIFx1YzYyNFx1Yjc5Y1x1YjljY1x1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOWQxXHVjNWQwXHVjMTFjIFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWNkZThcdWQ1NThcdWIyOTQgXHViMGEwXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjYzQ1XHVjNzQ0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODE1XHViODJjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IFx1Y2M0NVx1Yzc0MCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YjRhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjYzQ1XHVjNzQwIFx1YWMwMFx1YzdhNSBcdWJjMTFcdWM1ZDAgXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjYzQ1XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1Y2M0NSBcdWQ1NThcdWIwOThcdWI5N2MgXHViZTgwIFx1YjJlNFx1Yzc0YywgXHVhYzAwXHVjN2E1Jm5ic3A7XHVjNzA0XHVjNWQwIFx1YjE5M1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M0NVx1Yzc0MCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1Y2M0NSBcdWM3NzRcdWI5ODRcdWM3NTggXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiAxXHVjNzQwIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzExY1x1YjI5NCBcdWNjNDVcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjNzA0XHVjNWQwXHVjMTFjXHViZDgwXHVkMTMwIFx1Y2M0NVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjNzdkXHVjNzNjXHViYTc0ICgxLCAyLCAuLi4sIE4pXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1Y2M0NVx1Yzc3NCAzXHVhZDhjXHVjNzg4XHVhY2UwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCAoMywgMiwgMSlcdWI4NWMgXHVjMzEzXHVjNWVjXHVjNzg4XHVjNzQ0IFx1YjU0YywgMlx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1Y2M0NVx1Yzc0NCBcdWMzMTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YmEzY1x1YzgwMCwgMlx1YmM4OCBcdWNjNDVcdWM3NDQgXHViZTgwIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVhZGY4XHViODA3XHVhYzhjIFx1YjQxOFx1YmE3NCAoMiwgMywgMSlcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIDFcdWM3NDQgXHViZTgwIFx1YjJlNFx1Yzc0YyBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YjE5M1x1YzczY1x1YmE3NCAoMSwgMiwgMylcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgXHVjYzQ1XHVjNzc0IFx1YzViNFx1YjViYlx1YWM4YyBcdWMzMTNcdWM1ZWNcdWM3ODhcdWIyOTRcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YmM4OFx1YjljY1x1YzVkMCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YzMxM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjNDVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoTiAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNjNDVcdWJkODBcdWQxMzAgXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNjNDVcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE4NyBcdWJjODhcdWI5Y2NcdWM1ZDAgXHVjYzQ1XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS05KSUdFIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgYSBob21lIGxpYnJhcnkgY29uc2lzdGluZyBvZiBOIGJvb2tzIGFycmFuZ2VkIG9uZSBvbiB0b3Agb2YgdGhlIG90aGVyIGluIGEgbmFycm93IGNhYmluZXQuIFNpbmNlIGJlaW5nIHdlbGwgdHJhaW5lZCBpbiB0aGUgc2VjcmV0cyBvZiBhbHBoYWJldCBpbiB0aGUgcHJldmlvdXMgdGFzaywgaGUgbm93IHdpc2hlcyB0byBhcnJhbmdlIHRoZSBib29rcyBhbHBoYWJldGljYWxseSwgc28gdGhhdCB0aGUgYm9vayB3aG9zZSB0aXRsZSBjb21lcyBmaXJzdCBhbHBoYWJldGljYWxseSBlbmRzIHVwIG9uIHRvcCwgYW5kIHRoZSBhbHBoYWJldGljYWxseSBsYXN0IG9uZSBhdCB0aGUgYm90dG9tIG9mIHRoZSBwaWxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBjYW4gZWFzaWx5IHB1bGwgYSBib29rIG91dCBvZiB0aGUgY2FiaW5ldCwgYnV0IGl0IGlzIGRpZmZpY3VsdCB0byBwdXNoIGl0IGJhY2sgaW50byB0aGUgcGlsZSwgc28gdGhlIGJvb2sgY2FuIG9ubHkgYmUgcmV0dXJuZWQgdG8gdGhlIHRvcCBvZiB0aGUgcGlsZS4gVGh1cywgdGhlIG9ubHkgYXZhaWxhYmxlIG1ldGhvZCBvZiBzb3J0aW5nIHRoZSBib29rcyBpcyByZXBlYXRlZGx5IHB1bGxpbmcgYSBib29rIG91dCBvZiB0aGUgcGlsZSBhbmQgcGxhY2luZyBpdCBvbiB0b3Agb2YgdGhlIHBpbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBib29rcyBhcmUgbGFiZWxsZWQgd2l0aCBpbnRlZ2VycyBmcm9tIDEgdG8gTiwgaW4gYWxwaGFiZXRpY2FsIG9yZGVyLiBUaGVyZWZvcmUsIE1pcmtvIHdhbnRzIHRoZW0gdG8gYmUgb3JkZXJlZCBhcyAoMSwgMiwgLi4uLCBOKSwgY291bnRpbmcgZnJvbSB0aGUgdG9wLiBGb3IgZXhhbXBsZSwgaWYgTiA9IDMgYW5kIHRoZSBzdGFydGluZyBvcmRlciBpcyAoMywgMiwgMSksIHR3byBtb3ZlcyBhcmUgc3VmZmljaWVudC4gRmlyc3QsIGhlIHB1bGxzIG91dCB0aGUgYm9vayBudW1iZXIgMiBhbmQgcGxhY2VzIGl0IG9uIHRvcCwgc28gdGhlIHBpbGUgYmVjb21lcyAoMiwgMywgMSkuIEFmdGVyIHRoYXQsIGhlIGRvZXMgdGhlIHNhbWUgd2l0aCBib29rIG51bWJlciAxLCB0aHVzIHRoZSBwaWxlIGJlY29tZXMgKDEsIDIsIDMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZWxwIE1pcmtvIGJ5IGNhbGN1bGF0aW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3ZlcyBuZWVkZWQgdG8gc29ydCBhIGdpdmVuIHN0YXJ0aW5nIG9yZGVyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoTiAmbGU7IDMwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlci4gVGhlc2UgTiBpbnRlZ2VycyByZXByZXNlbnQgdGhlIG9yZGVyIG9mIE1pcmtvJnJzcXVvO3MgYm9va3MgZnJvbSB0b3AgdG8gYm90dG9tIG9mIHRoZSBjYWJpbmV0LiBFYWNoIG9mIHRoZSBpbnRlZ2VycyAxLCAyLCAuLi4sIE4gYXBwZWFycyBleGFjdGx5IG9uY2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbWluaW11bSBudW1iZXIgb2YgbW92ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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