题目描述

Kevin 有 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，它们按环形排列。对于环上的数字，数字 $a_i$ 和 $a_{i+1} \ (1 \leq i < n)$ 是相邻的，且数字 $a_1$ 和 $a_n$ 是相邻的。因此，每个数字有恰好两个相邻的数字。

在 $1$ 分钟内，Kevin 可以将 $a_i$ 修改为这 $3$ 个数字中的最小值或最大值：$a_i$ 以及它的两个相邻数字。例如，如果 $a_i=5$ 且 $a_i$ 的两个相邻数字为 $3$ 和 $2$，Kevin 修改 $a_i$ 为最小值后，$a_i$ 会变为 $2$；如果 Kevin 修改 $a_i$ 为最大值，$a_i$ 仍是 $5$。

对于从 $1$ 到 $m$ 的每个整数 $x$，计算出让上述环上的数字都变为 $x$ 的最短时间。

输入格式

第一行包含两个整数 $n$ 和 $m \ (3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$，代表环上的数字个数和需要计算答案的 $x$ 的范围。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq m)$，代表环上的数字。

输出格式

输出 $m$ 个整数。第 $i$ 个整数为将环上的所有数字变为 $i$ 的最短时间的分钟数，如果无论如何都无法将环上的所有整数变为 $i$，则第 $i$ 个整数应输出 $-1$。

7 5
2 5 1 1 2 3 2

5 5 7 -1 6

提示

要让环上的所有整数都变为 $2$，Kevin 需要至少 $5$ 分钟。一种可行的修改方案为：

1. 将 $a_6$ 修改为它与相邻数字中的最小值，即修改为 $2$；
2. 将 $a_4$ 修改为它与相邻数字中的最大值，即修改为 $2$；
3. 将 $a_3$ 修改为它与相邻数字中的最大值，即修改为 $5$；
4. 将 $a_2$ 修改为它与相邻数字中的最小值，即修改为 $2$；
5. 将 $a_3$ 修改为它与相邻数字中的最小值，即修改为 $2$。