|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||2||2||2||100.000%|
Mirko is playing an extremely interesting game.
He has a deck of N cards (numbered 1 to N) such that no two cards have the same number. The deck has been shuffled.
Mirko starts with the first card and traverses through the deck until reaching the card with number 1 which he then removes from the deck. After that he searches and removes each of the cards numbered 2, 3, 4, etc. always starting from the place where he has found the previously removed card. Each time he reaches the end of the deck he claps his hands and starts again from the beginning of the deck. This procedure will eventually empty the deck and once the last card (the one numbered N) has been removed the game is over.
Write a program that, given an initial shuffling of deck, finds the number of times Mirko will clap his hands during the game.
First line of the input file contains an integer N, the number of cards in the deck, 1 ≤ N ≤ 100000. The next N lines contain numbers of cards given in order of their appearance in the initial shuffling.
The only line of the output file should contain the requested number of claps as defined above.
5 3 5 1 4 2
3 2 1 3
7 3 6 7 1 5 4 2