У Кевина есть n целых чисел a1, a2, ..., an, расположенных по кругу. То есть числа ai и ai+1 (1 ≤ i < n) являются соседними. Числа a1 и an также являются соседями. Следовательно, у каждого числа ровно два соседа.

За одну минуту Кевин может установить ai равным минимальному из трех чисел: ai и два его соседа. В качестве альтернативы Кевин может установить ai равным максимуму среди тех же чисел. Например, если ai = 5 и ai имеет двух соседей 3 и 2, и Кевин выполняет минимальную операцию, ai будет равно 2. Однако, если он выполнит максимальную операцию, ai останется равным 5.

Для каждого x от 1 до m найдите минимальное количество минут, за которое все числа будут равны x, или определите, что это невозможно.

Входные данные

Первая строка содержит два целых числа n и m (3 ≤ n ≤ 2 * 105, 1 ≤ m ≤ 2 * 105) — количество целых чисел в круге и количество целых чисел, для которых нужно найти ответы.

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ m) - целые числа по кругу.

Выходные данные

Выведите m целых чисел. i-е целое число должно быть равно минимальному количеству минут, необходимых для того, чтобы все числа стали равными i или -1, если это невозможно.

Пояснение

Чтобы все числа были равны 2, Кевину нужно как минимум 5 минут. Одна из возможных последовательностей операций:

1. Примените операцию min к a6, она будет равна 2.
2. Примените операцию max к a4, она будет равна 2.
3. Примените операцию max к a3, она будет равна 5.
4. Примените операцию min к a2, она будет равна 2.
5. Примените операцию min к a3, она будет равна 2.