問題一覧 > 通常問題

No.3441 Sort Permutation 2

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 63
作問者 : 👑 potato167 / テスター : noya2
お気に入りにしたユーザー ProblemId : 13002 / 自分の提出
問題文最終更新日: 2026-02-05 18:13:32
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 492 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ and a permutation $P = (P_{1},P_{2},\dots,P_{N})$ of $(1, 2, \dots, N)$.

For each of $k = 1, 2, \dots, N - 1$, answer the following question.


Alice sorts $P$ in ascending order by repeating the following operation.

  • Choose integers $i, j(i\neq j)$ between $1$ and $N$, inclusive, and swap $P_{i}$ and $P_{j}$. If $|i - j|$ is a multiple of $k$, Alice takes $1$ damage.

Alice sorts $P$ in ascending order with the minimum number of operations and, subject to that, acts so as to minimize the damage she takes.

Find the total damage Alice takes.

Constraints

  • $2\leq N\leq 2\times 10^{5}$
  • $(P_{1}, P_{2},\dots,P_{N})$ is a permutation of $(1,2,\dots,N)$
  • All input values are integers

Input

$N$
$P_{1}$ $P_{2}$ $\dots$ $P_{N}$

Output

Print $N - 1$ lines.

On the $i$-th line, print the answer for $k = i$.

Sample

Sample 1
Input
6
6 4 5 2 3 1
Output
3
2
0
0
1

Consider the answer for $k = 2$.

For example, $P$ can be sorted in ascending order with the following $3$ operations.

  • Operate with $(i, j) = (2, 4)$. After the operation, $P = (6, 2, 5, 4, 3, 1)$.
  • Operate with $(i, j) = (1, 6)$. After the operation, $P = (1, 2, 5, 4, 3, 6)$.
  • Operate with $(i, j) = (3, 5)$. After the operation, $P = (1, 2, 3, 4, 5, 6)$.

Among the above $3$ operations, Alice takes $1$ damage on each of the $1$st and $3$rd operations, so she takes $2$ damage in total.

Operating in this way is one of the ways to sort $P$ in ascending order with the minimum number of operations while minimizing the total damage taken, so print $2$ on the $2$nd line.

Sample 2
Input
4
1 2 3 4
Output
0
0
0
Sample 3
Input
11
10 8 5 11 7 6 3 2 4 1 9
Output
6
3
2
0
0
1
0
0
1
0

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