問題文

猫たちが1～ｎまでの数直線上の整数座標に１匹ずつ全部でｎ匹います。
猫たちはどの猫も今いる座標から目的の整数座標へ移動します。
猫たちはすれ違うたびに挨拶をします。
全猫はいっせいに移動を始め、全員が一定速度で移動します、合計何回の挨拶が交わされるでしょうか。移動のデータが与えられるので挨拶回数を求めましょう。

目的の整数座標に先に到達した猫はそこで待機してすれ違うたびに挨拶をします。
猫たちはすれ違うか同じ座標になれば礼儀正しいので必ず１対１で挨拶をします。
つまり、ｍ匹の猫が同じ座標になれば、ｍ（ｍ-1）/２回挨拶が発生します。

2018/10/06 19:28 制約を 2.5秒に変更しました。

入力

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

Nは猫の数である。
$3 \le N \le 30000$
$M_i$は整数座標$i$の猫が整数座標$M_i$へ移動するという意味である。
$1 \le M_i \le N$
異なる$i$,$j$について$M_i \ne M_j$

出力

Ans 最後に改行してください。

サンプル

3
1
2
3

0

9
9
3
4
2
5
7
6
8
1

18