Migrated from Lutece 415 Hash Table

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl).

To help her friend Madoka save the world, Homura need to collect data, and she choose a kind of data structure called Hash Table.

I suppose all of you are familiar with the Hash Table (if not, you won't take part in the competition!), for a piece of data $D$, the Hash Function $H$ gives a Hash Key: $H(D)$, and the data will be stored in Hash Table $[H(D)]$. For two pieces of data $D_1$ and $D_2$, if their Hash Keys are the same ($H(D_1) = H(D_2)$), we say an COLLUSION occurs. $D_1$ and $D_2$ cannot be stored in the same position of the Hash Table. The most convenient way to solve the problem is linear probing.

We assume that $D_1$ has been inserted into Hash Table $[H(D_1)]$, now if we need to insert $D_2$ into the Hash Table, since Hash Table $[H(D_1)]$ has been occupied by $D_1$, $D_2$ has to find the next position of $H(D_1)$: Hash Table $[H(D_1)+1]$. If Hash Table $[H(D_1)+1]$ is also occupied, $D_2$ has to find the next position of $H(D_1)+1$: Hash Table $[H(D_1)+1]$ ... Till $D_2$ finds an unoccupied position: Hash Table $[p]$, and be stored in it.

As It is known that Homura has magic that can control time, she can rearrange the order that data is inserted into the Hash Table in. Given $N$ Hash Keys $H(D_1), H(D_2),\cdots , H(D_N)$ of data $D_1, D_2,\cdots , D_N$, your task is to help her rearrange the order to minimize the total collusion times. You may assume the length of the Hash Table is infinitive.

Input

The first line contains an integer $N$ ($1\leq N\leq 10^6$).

The second line contains $N$ integers $D_1, D_2, \cdots , D_N$ ($1\leq D_i\leq 2^{31}-1$).

Output

The minimum of total collusion times.

Samples

5
1 2 1 3 2

6

Note

Huge input. scanf recommended.

Resources

5th BUPT Programming Contest Preliminary