No.694 square1001 and Permutation 3

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 257 MB / 通常問題
タグ : / 解いたユーザー数 46
作問者 : square1001square1001 / テスター : 37zigen37zigen

1 ProblemId : 2111 / 出題時の順位表

Note

正当判定に1分程かかります。ご注意ください。

問題文

square1001 は, 長さ $N$ の数列 $A = (A_0, A_1, A_2, \dots, A_{N-1})$ を見つけた.

John と Brus は, 数列 $v = (A_{k \ mod \ N}, A_{(k + 1) \ mod \ N}, A_{(k + 2) \ mod \ N}, \dots, A_{(k + N - 1) \ mod \ N})$ に対して次のようなプログラムを実行して, すべての $k$ について最終的な $cnt$ の値をすぐに求めた.

cnt = 0
for i = 0 to N-1
    for j = 0 to N-2
        if v[j] > v[j+1]
            v[j] と v[j+1] を交換
            cnt に 1 を加算する

しかし, John と Brus と, 彼らの書いたコードは消えてしまった. あなたは彼に代わってこの問題を解くプログラムを書かなければならない.

入力

$N$
$A_0$
$A_1$
$A_2$
 : 
$A_{N-1}$

  • 1 行目には, 数列の長さ $N$ が与えられる.
  • $i + 2 \ (0 \le i < N)$ 行目には, 数列 $i$ 番目の値 $A_i$ が与えられる.

出力

$i+1 \ (0 \le i < N)$ 行目に, 数列 $v = (A_{i \ mod \ N}, A_{(i + 1) \ mod \ N}, A_{(i + 2) \ mod \ N}, \dots, A_{(i + N - 1) \ mod \ N})$ に対して上のようなプログラムを実行させたときの最終的な $cnt$ の値を出力しなさい.

制約

  • $1 \le N \le 500 \ 000$.
  • $1 \le A_i \le 1 \ 000 \ 000 \ 000 \ (0 \le i < N)$.

サンプル

サンプル1
入力
5
2
5
1
4
3
出力
5
7
3
7
5

例えば, 数列 $(2, 5, 1, 4, 3)$ に対してプログラムを実行させると, 数列は次のように変化します.

  • $(2, 5, 1, 4, 3)$ → $(2, 1, 5, 4, 3)$ → $(2, 1, 4, 5, 3)$ → $(2, 1, 4, 3, 5)$ → $(1, 2, 4, 3, 5)$ → $(1, 2, 3, 4, 5)$

$5$ 回変化したので, 最終的な $cnt$ の値は $5$ です.

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

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