P5797 [SEERC 2019] Max or Min

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$.

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 $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.

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