Max or Min#11274
Kevin has integers a_1, a_2, ..., a_n arranged in a circle. That is, the numbers a_i and a_{i+1} ( ≤ < ) 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 its two neighbors. Alternatively, Kevin can set a_i to the maximum among the same numbers. For example, if a_i = 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 ( ≤ ≤ 2 \cdot 10^5, ≤ ≤ 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, ..., a_n ( ≤ a_i ≤ ) - 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 .