No.694 square1001 and Permutation 3
タグ : / 解いたユーザー数 87
作問者 :
37zigen
Note
Judging takes about 1 minute. Please be aware of this.Problem Statement
square1001 found a sequence $A = (A_0, A_1, A_2, \dots, A_{N-1})$ of length $N$.
John and Brus ran the following program on the sequence $v = (A_{k \ mod \ N}, A_{(k + 1) \ mod \ N}, A_{(k + 2) \ mod \ N}, \dots, A_{(k + N - 1) \ mod \ N})$ and immediately found the final value of $cnt$ for every $k$.
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 を加算する
However, John, Brus, and the code they wrote have disappeared. You must write a program that solves this problem in their place.
Input
$N$
$A_0$
$A_1$
$A_2$
:
$A_{N-1}$
- The first line contains the length $N$ of the sequence.
- Line $i + 2 \ (0 \le i < N)$ contains the $i$-th value $A_i$ of the sequence.
Output
On line $i+1 \ (0 \le i < N)$, output the final value of $cnt$ when the above program is run on the sequence $v = (A_{i \ mod \ N}, A_{(i + 1) \ mod \ N}, A_{(i + 2) \ mod \ N}, \dots, A_{(i + N - 1) \ mod \ N})$.
Constraints
- $1 \le N \le 500 \ 000$.
- $1 \le A_i \le 1 \ 000 \ 000 \ 000 \ (0 \le i < N)$.
Sample
Sample 1
Input
5 2 5 1 4 3
Output
5 7 3 7 5
For example, when the program is run on the sequence $(2, 5, 1, 4, 3)$, the sequence changes as follows.
- $(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)$
The sequence changed $5$ times, so the final value of $cnt$ is $5$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。