Kevin has $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ arranged in a circle. That is, the numbers $$$a_i$$$ and $$$a_{i+1}$$$ ($$$1 \leq i < n$$$) are neighbors. The numbers $$$a_1$$$ and $$$a_n$$$ are neighbors as well. Therefore, each number has exactly two neighbors.
In one minute, Kevin can set $$$a_i$$$ to the minimum among three numbers: $$$a_i$$$ and it's two neighbors. Alternatively, Kevin can set $$$a_i$$$ to the maximum among the same numbers. For example, if $$$a_i = 5$$$ and $$$a_i$$$ has two neighbors $$$3$$$ and $$$2$$$, and Kevin performs the minimum operation, $$$a_i$$$ will be equal to $$$2$$$. However, if he performs the maximum operation, $$$a_i$$$ will remain $$$5$$$.
For each $$$x$$$ from $$$1$$$ to $$$m$$$, find the minimum number of minutes to make all numbers equal $$$x$$$, or determine that it is impossible to do so.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — the number of integers in the circle, and the number of integers you need to find answers for.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the integers in the circle.
Print $$$m$$$ integers. The $$$i$$$-th integer should be equal to the minimum number of minutes that are needed to make all numbers equal $$$i$$$ or $$$-1$$$ if it's impossible.
7 5 2 5 1 1 2 3 2
5 5 7 -1 6
To make all numbers equal $$$2$$$ Kevin needs at least $$$5$$$ minutes. One of the possible sequence of operations:
