問題一覧 > 通常問題

No.694 square1001 and Permutation 3

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 257 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 : square1001square1001 / テスター : 37zigen37zigen
2 ProblemId : 2111 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-06-08 23:18:15

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$ です.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。