No.742 にゃんにゃんにゃん 猫の挨拶

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 69
作問者 : horiesinitihoriesiniti / テスター : はむこはむこ
0 ProblemId : 2147 / 出題時の順位表

問題文

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

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

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 最後に改行してください。

サンプル

サンプル1
入力
3
1
2
3
出力
0

どの猫も初期位置から動かない、当然挨拶もない、猫たちは昼寝をしているようだ。

サンプル2
入力
9
9
3
4
2
5
7
6
8
1
出力
18

注目すべき点は2,3マス目の猫は相手を追い抜かないので互いにあいさつしない。 1マスめの猫は2や3マス目の待機状態の猫とすれ違うので挨拶が発生する。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。