Problem Statement

There are n cats in total, one at each integer coordinate from 1 to n on a number line.
Every cat moves from its current coordinate to its destination integer coordinate.
The cats greet each other every time they pass each other.
All the cats start moving at the same time, and each of them moves at a constant speed. How many greetings are exchanged in total? Given the movement data, find the number of greetings.

A cat that reaches its destination integer coordinate first waits there and greets every time another cat passes it.
The cats are polite, so whenever they pass each other or end up at the same coordinate, they always greet one-on-one.
That is, if m cats are at the same coordinate, m(m-1)/2 greetings occur.

2018/10/06 19:28 The constraint was changed to 2.5 seconds.

Input

$N$
$M_1$
$\dots$
$M_i$
$\dots$
$M_n$

N is the number of cats.
$3 \le N \le 30000$
$M_i$ means that the cat at integer coordinate $i$ moves to integer coordinate $M_i$.
$1 \le M_i \le N$
For distinct $i$,$j$, $M_i \ne M_j$

Output

Ans Print a newline at the end.

Sample

3
1
2
3

0

9
9
3
4
2
5
7
6
8
1

18