A command-line interface (CLI) is one of the oldest human-computer interface types in existence. A CLI allows interaction with the software through a command interpreter and is usually accessible in a text terminal (or window). The advantage of a command interpreter is that it allows the user to operate the system using only the keyboard. Even today, where we are accustomed to sophisticated graphical interfaces, many applications and operating systems include some kind of command-line interface, and many users still prefer to use it for most tasks. One of the most useful features of a command interpreter is the command history. When a command is entered and executed, it is placed in the command history of the terminal.
The command can be displayed again in the terminal by pressing the '↑' key; the Enter key executes the command again when the command is being displayed on the terminal. All the commands executed are stored in the history: pressing the '↑' key twice shows the penultimate command executed, pressing it three times displays the third-last command, and so on. For example, if the initial history is (A, B, C, D), to repeat the C command simply press the '↑' key twice. The history will then be updated to (A, B, C, D, C). At this point, to repeat command A, it is necessary to press the '↑' key five times; the history will be updated to (A, B, C, D, C, A). At this point, to repeat command A once more, press the '↑' key once; the history will be updated to (A, B, C, D, C, A, A). Leandro is a systems administrator and often uses the command interpreter to remotely manage the servers that he manages. In general, he just needs to repeat commands that he had typed before. While working on a server, he had a curiosity: how many times does he need to press the '↑' key to execute a given sequence of commands? He knows what position in the command history he needs to execute, but he doesn't know how to solve this problem. So he asked you to do a program that would answer his question.
Input
The input is composed of several test cases. The first line of each test case contains an integer N, indicating the number of commands Leandro wants to execute (1 ≤ N ≤ 1,000). The second line of a test case contains N integers P1, P2,. . . , PN, which indicate the positions of the commands in the history (1 ≤ Pi ≤ 1,000,000) at the initial moment, in the order in which the commands are to be executed. That is, the first command to be executed is initially in position P1 of the history; then the command that is initially in position P2 in the history, and so on, until PN, which is the starting position of the last command to be executed, must be executed. Note that there may be Pi = Pj. The positions are given as a function of the number of times the '↑' key must be pressed: a command in position 5 requires the '↑' key to be pressed five times before it appears on the terminal (note that as commands are executed, the position of a given command in the history may change). The end of the entry is indicated by N = 0.
Output
For each test case, your program must print a single line containing the number of times Leandro need to press the '↑' key to execute all commands.
| Input Sample |
Output Sample |
|
3
2 5 3
4
2 1 4 3
5
1 2 3 4 5
4
1 3 1 3
0
|
13
16
25
9
|
Brazil