問題一覧 > 通常問題

No.694 square1001 and Permutation 3

レベル : / AI推定難易度 : 1275 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 257 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 87
作問者 : square1001 / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 2111 / 自分の提出
問題文最終更新日: 2026-06-26 04:11:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 192 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。