Circular Array Transformation

Kevin has n integers \(a_1, a_2, \dots, a_n\) arranged in a circle. In other words, for \(1 \le i < n\), \(a_i\) and \(a_{i+1}\) are adjacent, and additionally \(a_1\) and \(a_n\) are adjacent. Therefore, each number has exactly two neighbors.

In one minute, Kevin can select an index \(i\) and update \(a_i\) to either the minimum or the maximum of the three numbers: \(a_{i-1}\), \(a_i\), and \(a_{i+1}\) (indices are taken modulo \(n\)). For example, if \(a_i=5\) and its two neighbors are \(3\) and \(2\), then choosing the minimum will change \(a_i\) to \(2\), while choosing the maximum will leave it as \(5\).

For every integer \(x\) from \(1\) to \(m\), compute the shortest time (in minutes) required to make every number in the circle become \(x\>.

Note: It is only possible to change the circle to a target value \(x\) if either the circle is already all \(x\), or \(x\) is equal to the global minimum or global maximum of the initial array. Otherwise, it is impossible to obtain \(x\) because the operation can only set a number to the minimum or maximum of a triple. When the transformation is impossible, output \(-1\).

The optimal strategy is to update each non-\(x\) element one by one. Hence, if the array is not already uniform and \(x\) is equal to the global minimum or global maximum, the minimum time will be equal to the number of elements not already equal to \(x\) (i.e., \(n - (\text{number of occurrences of } x)\)).

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output \(m\) space‐separated integers. The \(i\)-th integer (for \(1 \le i \le m\)) represents the minimum number of minutes needed to convert the entire circular array to \(x=i\). If it is impossible to achieve, output \(-1\) for that \(x\).

sample

3 5
5 3 5

-1 2 -1 1 -1