Max or Min#12799

Max or Min

1 second
256 megabytes
Very hard

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.

Input

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.

Output

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.

Examples

Example 1

Loading
Loading

Note

To make all numbers equal Kevin needs at least minutes. One of the possible sequence of operations:

  1. Apply min operation to a_6, it will be equal to .

  2. Apply max operation to a_4, it will be equal to .

  3. Apply max operation to a_3, it will be equal to .

  4. Apply min operation to a_2, it will be equal to .

  5. Apply min operation to a_3, it will be equal to .