시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 143 74 51 45.133%

문제

동현이는 아주 재미있는 놀이를 하고 있다.

동현이는 1부터 N까지의 서로 다른 숫자가 쓰여 있는 N개의 카드를 가지고 있다. 동현이는 이 카드를 섞어서 한 줄로 늘어 놓은 후, 왼쪽부터 오른쪽까지 카드를 훑어 보면서 1이 적힌 카드를 발견하면 그 카드를 빼낸다. 그 다음에는 1이 있던 위치부터 시작하여 2가 적힌 카드를 발견할 때까지 오른쪽으로 간다. 2가 적힌 카드를 빼내면 거기서부터 다시 3이 적힌 카드를 발견할 때까지 오른쪽으로 간다. 이런 식으로 모든 카드를 빼낼 때까지 반복하는데, 중간에 카드 줄의 가장 오른쪽에 도달할 경우에는 (왜인지는 모르겠지만) 박수를 치고 다시 가장 왼쪽으로 돌아간다.

동현이는 게임이 끝날 때까지 자신이 박수를 몇 번 칠지 알고 싶어한다. 동현이를 도와, 처음 카드를 늘어놓은 상태가 주어질 때 박수 횟수를 구해주자!

입력

입력의 첫 번째 줄에는 카드의 수를 나타내는 정수 N (1 ≤ N ≤ 100000)이 주어진다. 다음 N줄에 걸쳐 늘어놓은 카드의 번호가 왼쪽부터 오른쪽 순서대로 주어진다.

출력

동현이가 게임이 끝날 때까지 치는 박수의 횟수를 정수 하나로 출력한다.

예제 입력 1

5
3
5
1
4
2

예제 출력 1

2

예제 입력 2

3
2
1
3

예제 출력 2

1

예제 입력 3

7
3
6
7
1
5
4
2

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjMyMzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWI0ZGNcdWIxODBcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWM4ZmMgXHVjN2FjXHViYmY4XHVjNzg4XHViMjk0IFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDRcdWM3NzRcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViM2Q5XHVkNjA0XHVjNzc0XHViMjk0IFx1Yzc3NCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjMTFlXHVjNWI0XHVjMTFjIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHViMjk4XHVjNWI0IFx1YjE5M1x1Yzc0MCBcdWQ2YzQsIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWFlNGNcdWM5YzAgXHVjZTc0XHViNGRjXHViOTdjIFx1ZDZkMVx1YzViNCBcdWJjZjRcdWJhNzRcdWMxMWMgMVx1Yzc3NCBcdWM4MDFcdWQ3OGMgXHVjZTc0XHViNGRjXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU1OFx1YmE3NCBcdWFkZjggXHVjZTc0XHViNGRjXHViOTdjIFx1YmU3Y1x1YjBiOFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCAxXHVjNzc0IFx1Yzc4OFx1YjM1OCBcdWM3MDRcdWNlNThcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIDJcdWFjMDAgXHVjODAxXHVkNzhjIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDRcdWIyZTQuIDJcdWFjMDAgXHVjODAxXHVkNzhjIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWJlN2NcdWIwYjRcdWJhNzQgXHVhYzcwXHVhZTMwXHVjMTFjXHViZDgwXHVkMTMwIFx1YjJlNFx1YzJkYyAzXHVjNzc0IFx1YzgwMVx1ZDc4YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHViYzFjXHVhY2FjXHVkNTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzA0XHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVjMmRkXHVjNzNjXHViODVjIFx1YmFhOFx1YjRlMCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHViZTdjXHViMGJjIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMThcdWJjZjVcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWNlNzRcdWI0ZGMgXHVjOTA0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAoXHVjNjVjXHVjNzc4XHVjOWMwXHViMjk0IFx1YmFhOFx1Yjk3NFx1YWNhMFx1YzljMFx1YjljYykgXHViYzE1XHVjMjE4XHViOTdjIFx1Y2U1OFx1YWNlMCBcdWIyZTRcdWMyZGMgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNkOVx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMGEwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViYzE1XHVjMjE4XHViOTdjIFx1YmE4NyBcdWJjODggXHVjZTYwXHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwNFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAsIFx1Y2M5OFx1Yzc0YyBcdWNlNzRcdWI0ZGNcdWI5N2MgXHViMjk4XHVjNWI0XHViMTkzXHVjNzQwIFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1YmMxNVx1YzIxOCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHVjOGZjXHVjNzkwITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViMjk4XHVjNWI0XHViMTkzXHVjNzQwIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjNkOVx1ZDYwNFx1Yzc3NFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMGEwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWNlNThcdWIyOTQgXHViYzE1XHVjMjE4XHVjNzU4IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMjMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS1JVRyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaXMgcGxheWluZyBhbiBleHRyZW1lbHkgaW50ZXJlc3RpbmcgZ2FtZS48XC9wPlxyXG5cclxuPHA+SGUgaGFzIGEgZGVjayBvZiBOIGNhcmRzIChudW1iZXJlZCAxIHRvIE4pIHN1Y2ggdGhhdCBubyB0d28gY2FyZHMgaGF2ZSB0aGUgc2FtZSBudW1iZXIuIFRoZSBkZWNrIGhhcyBiZWVuIHNodWZmbGVkLjxcL3A+XHJcblxyXG48cD5NaXJrbyBzdGFydHMgd2l0aCB0aGUgZmlyc3QgY2FyZCBhbmQgdHJhdmVyc2VzIHRocm91Z2ggdGhlIGRlY2sgdW50aWwgcmVhY2hpbmcgdGhlIGNhcmQgd2l0aCBudW1iZXIgMSB3aGljaCBoZSB0aGVuIHJlbW92ZXMgZnJvbSB0aGUgZGVjay4gQWZ0ZXIgdGhhdCBoZSBzZWFyY2hlcyBhbmQgcmVtb3ZlcyBlYWNoIG9mIHRoZSBjYXJkcyBudW1iZXJlZCAyLCAzLCA0LCBldGMuIGFsd2F5cyBzdGFydGluZyBmcm9tIHRoZSBwbGFjZSB3aGVyZSBoZSBoYXMgZm91bmQgdGhlIHByZXZpb3VzbHkgcmVtb3ZlZCBjYXJkLiBFYWNoIHRpbWUgaGUgcmVhY2hlcyB0aGUgZW5kIG9mIHRoZSBkZWNrIGhlIGNsYXBzIGhpcyBoYW5kcyBhbmQgc3RhcnRzIGFnYWluIGZyb20gdGhlIGJlZ2lubmluZyBvZiB0aGUgZGVjay4gVGhpcyBwcm9jZWR1cmUgd2lsbCBldmVudHVhbGx5IGVtcHR5IHRoZSBkZWNrIGFuZCBvbmNlIHRoZSBsYXN0IGNhcmQgKHRoZSBvbmUgbnVtYmVyZWQgTikgaGFzIGJlZW4gcmVtb3ZlZCB0aGUgZ2FtZSBpcyBvdmVyLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gYW4gaW5pdGlhbCBzaHVmZmxpbmcgb2YgZGVjaywgZmluZHMgdGhlIG51bWJlciBvZiB0aW1lcyBNaXJrbyB3aWxsIGNsYXAgaGlzIGhhbmRzIGR1cmluZyB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgYW4gaW50ZWdlciBOLCB0aGUgbnVtYmVyIG9mIGNhcmRzIGluIHRoZSBkZWNrLCAxICZsZTsgTiAmbGU7IDEwMDAwMC4gVGhlIG5leHQgTiBsaW5lcyBjb250YWluIG51bWJlcnMgb2YgY2FyZHMgZ2l2ZW4gaW4gb3JkZXIgb2YgdGhlaXIgYXBwZWFyYW5jZSBpbiB0aGUgaW5pdGlhbCBzaHVmZmxpbmcuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUgc2hvdWxkIGNvbnRhaW4gdGhlIHJlcXVlc3RlZCBudW1iZXIgb2YgY2xhcHMgYXMgZGVmaW5lZCBhYm92ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 2번

  • 문제를 번역한 사람: kdh9949
  • 잘못된 데이터를 찾은 사람: movie_jo