Description

Kevin has $n$ integers $a_1, a_2, \dots, a_n$, arranged in a circular order. On the circle, the numbers $a_i$ and $a_{i+1}$ $(1 \leq i < n)$ are adjacent, and $a_1$ and $a_n$ are adjacent. Therefore, each number has exactly two adjacent numbers.

In 1 minute, Kevin can change $a_i$ to the minimum or the maximum among these three numbers: $a_i$ and its two adjacent numbers. For example, if $a_i = 5$ and its two adjacent numbers are $3$ and $2$, then after changing $a_i$ to the minimum, $a_i$ becomes $2$; if Kevin changes $a_i$ to the maximum, then $a_i$ is still $5$.

For each integer $x$ from $1$ to $m$, compute the shortest time to make all numbers on the circle become $x$.

Input Format

The first line contains two integers $n$ and $m$ $(3 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$, representing the number of integers on the circle and the range of $x$ for which answers are required.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq m)$, representing the numbers on the circle.

Output Format

Output $m$ integers. The $i$-th integer is the minimum number of minutes needed to make all numbers on the circle equal to $i$. If it is impossible to make all integers become $i$, output $-1$ for the $i$-th integer.

7 5
2 5 1 1 2 3 2

5 5 7 -1 6

Hint

To make all integers on the circle become $2$, Kevin needs at least $5$ minutes. One feasible sequence of operations is:

1. Change $a_6$ to the minimum among it and its adjacent numbers, i.e., change it to $2$.
2. Change $a_4$ to the maximum among it and its adjacent numbers, i.e., change it to $2$.
3. Change $a_3$ to the maximum among it and its adjacent numbers, i.e., change it to $5$.
4. Change $a_2$ to the minimum among it and its adjacent numbers, i.e., change it to $2$.
5. Change $a_3$ to the minimum among it and its adjacent numbers, i.e., change it to $2$.

Translated by ChatGPT 5