Max или Min
Max или Min
У Кевина есть 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 минут. Одна из возможных последовательностей операций:
- Примените операцию min к
a6
, она будет равна 2. - Примените операцию max к
a4
, она будет равна 2. - Примените операцию max к
a3
, она будет равна 5. - Примените операцию min к
a2
, она будет равна 2. - Примените операцию min к
a3
, она будет равна 2.
7 5 2 5 1 1 2 3 2
5 5 7 -1 6