17955번 - Max or Min 다국어

Kevin has n integers a₁, a₂, . . . , a_n arranged in a circle. That is, the numbers a_i and a_i+1 (1 ≤ i < n) are neighbors. The numbers a₁ 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 ≤ n ≤ 2 · 10⁵, 1 ≤ m ≤ 2 · 10⁵) — 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₁, a₂, . . . , a_n (1 ≤ a_i ≤ 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.

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

1. Apply min operation to a₆, it will be equal to 2.
2. Apply max operation to a₄, it will be equal to 2.
3. Apply max operation to a₃, it will be equal to 5.
4. Apply min operation to a₂, it will be equal to 2.
5. Apply min operation to a₃, it will be equal to 2.