样例下载

题目描述

一个圆盘被分成 $n$ 个扇形格，依次编号为 $1$ ~ $n$，编号为 $i$ 的扇形格中写有一个整数 $A_i$。所有的整数都是不超过 $n$ 的正整数，即 $1 ≤ A_i ≤ n$。

圆盘中心有一个指针，初始时指向编号为 x 的扇形格。

你可以拨动指针。每次拨动，指针只能转动一格。拨动方向可以是顺时针，也可以是逆时针。

你希望指针指向圆盘上每个不同的整数至少一次。

问：你最少需要拨动指针多少次？

你需要输出当 $x=1, 2, ……, n$ 时对应的答案。

输入格式

第一行：一个整数 $n$。

第二行：$n$ 个整数 $A_i$。

输出格式

一行，$n$ 个整数，依次表示当 $x=1, 2, ……, n$ 时对应的答案。

样例输入

5
3 1 5 2 1

样例输入

3 4 3 3 4

样例解释

圆盘上有 5 个扇形格，包含 4 个不同的整数：1, 2, 3, 5

当 x=1 时，指针初始指向整数 3. 将指针始终顺时针拨动 3 次，或始终逆时针拨动 3 次，可使得 4 个不同的整数均被指向了一次。

当 x=2 时，指针初始指向整数 1. 将指针逆时针拨动一次指向3，顺时针拨动一次指向 1，再顺时针拨动两次，依次指向5, 2, 可使得 4 个不同的整数均被指向了至少一次。也可以将指针始终顺时针拨动 4 次，或者始终逆时针拨动 4 次。

其他略。

数据范围

• 20% 的数据：$n ≤ 500$
• 50% 的数据：$n ≤ 10^4$
• 100% 的数据：$1 ≤ n ≤ 5×10^5$，$1 ≤ A_i ≤ n$