У Кевина есть n целых чисел a[1]
, a[2]
, ..., a[n]
, расположенных по кругу. То есть числа a[i]
и a[i+1]
(1 ≤ i < n) являются соседними. Числа a[1]
и a[n]
также являются соседями. Следовательно, у каждого числа ровно два соседа.
За одну минуту Кевин может установить a[i]
равным минимальному из трех чисел: a[i]
и два его соседа. В качестве альтернативы Кевин может установить a[i]
равным максимуму среди тех же чисел. Например, если a[i]
= 5 и a[i]
имеет двух соседей 3 и 2, и Кевин выполняет минимальную операцию, a[i]
будет равно 2. Однако, если он выполнит максимальную операцию, a[i]
останется равным 5.
Для каждого x от 1 до m найдите минимальное количество минут, за которое все числа будут равны x, или определите, что это невозможно.
Первая строка содержит два целых числа n и m (3 ≤ n ≤ 2 * 10^5
, 1 ≤ m ≤ 2 * 10^5
) — количество целых чисел в круге и количество целых чисел, для которых нужно найти ответы.
Вторая строка содержит n целых чисел a[1]
, a[2]
, ..., a[n]
(1 ≤ a[i]
≤ m) - целые числа по кругу.
Выведите m целых чисел. i-е целое число должно быть равно минимальному количеству минут, необходимых для того, чтобы все числа стали равными i или -1, если это невозможно.
Чтобы все числа были равны 2, Кевину нужно как минимум 5 минут. Одна из возможных последовательностей операций:
Примените операцию min к a[6]
, она будет равна 2.
Примените операцию max к a[4]
, она будет равна 2.
Примените операцию max к a[3]
, она будет равна 5.
Примените операцию min к a[2]
, она будет равна 2.
Примените операцию min к a[3]
, она будет равна 2.