URI Online Judge | 2592

VaiNaSort

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

Professor Odracir Snitram studied various methods of ordering, as well as their respective complexities. One day, he decides to make a test, creating a method, with a box and N stones, numbered from 1 to N. The idea was to draw all the stones, one at a time, so that the sequence of numbers drawn was exactly 1 to N, that is, by drawing the number 1 first, then the number 2, then the 3, and so on, until the last one, which would be N. After drawing everything, if the attempt did not work, all the stones were Returned in the box, and the draw began again until it worked out. This method was named VaiNaSort!

Write a program that, given the amount of stones, and all attempts until you draw correctly, count the attempts.

Input

The input has several test cases. Each one starts with an integer N (2 ≤ N ≤ 10000), representing the amount of stones in the box. Next, there will be a few draw attempts, each formed with the numbers from 1 to N, in any order, until the expected order is achieved. The entry ends with N = 0.

Output

For each test case, print the total number of attempts.

Input Sample Output Sample

3
2 1 3
3 2 1
3 1 2
1 2 3
4
1 2 3 4
0

4
1