Kevin has 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 and , and Kevin performs the minimum operation, a_i will be equal to . However, if he performs the maximum operation, a_i will remain .
For each from to , find the minimum number of minutes to make all numbers equal , or determine that it is impossible to do so.
The first line contains two integers and (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 integers a_1, a_2, \ldots, a_n (1 \le a_i \le m) — the integers in the circle.
Print integers. The -th integer should be equal to the minimum number of minutes that are needed to make all numbers equal or if it's impossible.
Example 1
To make all numbers equal Kevin needs at least minutes. One of the possible sequence of operations:
Apply min operation to a_6, it will be equal to .
Apply max operation to a_4, it will be equal to .
Apply max operation to a_3, it will be equal to .
Apply min operation to a_2, it will be equal to .
Apply min operation to a_3, it will be equal to .