Note

問題文

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

John と Brus は, 数列 $v=(A_{kmodN},A_{(k+1)modN},A_{(k+2)modN},\dots ,A_{(k+N-1)modN})$ に対して次のようなプログラムを実行して, すべての $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_{imodN},A_{(i+1)modN},A_{(i+2)modN},\dots ,A_{(i+N-1)modN})$ に対して上のようなプログラムを実行させたときの最終的な $cnt$ の値を出力しなさい.

制約

• $1\le N\le 500000$.
• $1\le A_i\le 1000000000(0\le i<N)$.

サンプル

5
2
5
1
4
3

5
7
3
7
5