Max or Min

Kevin has n integers a[1], a[2], ..., a[n] arranged in a circle. That is, the numbers a[i] and a[i+1] (1 ≤ 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.

Input

The first line contains two integers n and m (3 ≤ n ≤ 2 * 10^5, 1 ≤ m ≤ 2 * 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], ..., a[n] (1 ≤ a[i] ≤ m) - the integers in the circle.

Output

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.

Examples

Note

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[6], it will be equal to 2.

2. Apply max operation to a[4], it will be equal to 2.

3. Apply max operation to a[3], it will be equal to 5.

4. Apply min operation to a[2], it will be equal to 2.

5. Apply min operation to a[3], it will be equal to 2.