시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 46 30 17 54.839%

문제

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

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

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

입력

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

출력

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

예제 입력

5
3
5
1
4
2

예제 출력

2

예제 입력 2

3
2
1
3

예제 출력 2

1

예제 입력 3

7
3
6
7
1
5
4
2

예제 출력 3

3

힌트

출처

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

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