beecrowd | 2539

High Five

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

The Nlogonian Basketball Team will play the final match of the Basketball World Cup, and the match is about to begin! Right now, the N players are warming up before entering the field.

Players are numbered from 1 to N. Initially, the players are arranged in a line in the edge of the field. The players will enter the field one at a time, in the same order as their number. Hence, player 1 is the first one to leave the line and enter the field. After that, player 2 will leave the line and enter the field, and so on.

When leaving the line, each player salutes every other player that are in front of him in the line with a high five. For example, consider that N=4 and the initial line is 3 1 2 4, where player 4 is the nearest one to the field. Player 1, while going to the field, will salute players 2 and 4 with a high five. Then, player 2 will salute with a high five only the player 4, and will then leave the line. Player 3 also salutes player 4 only (notice that both players 1 and 2 have left the line already). Finally, the last player does not salute anyone.

Your task is to determine the total number of high fives that will occur.

Input

The input contains several test cases. The first line of each test case contains the integer N (1 ≤ N ≤ 105). The second line contains N integers, indicating the order the players are initially in the line. The last integer given in the line is the nearest player to the field.

The input ends with end-of-file (EOF).

Output

For each test case, print a line containing the total number of high fives that will occur.

Input Sample Output Sample

4
3 1 2 4
5
5 4 3 2 1
5
1 2 3 4 5

4
0
10