Макс або Мін#11274

Макс або Мін

1 секунда

128 мегабайтів

Середня

У Кевіна є $n$ цілих чисел $a_{1}$ a_1, $a_{2}$ a_2, ..., $a_{n}$ a_n, розташованих по колу. Це означає, що числа $a_{i}$ a_i і $a_{i + 1}$ a_{i+1} ( $1 \leq i < n$ 1 \leq i < n) є сусідніми, а також $a_{1}$ a_1 і $a_{n}$ a_n є сусідами. Таким чином, кожне число має рівно два сусіди.

За одну хвилину Кевін може змінити $a_{i}$ a_i на мінімальне з трьох чисел: $a_{i}$ a_i і двох його сусідів. Або ж він може змінити $a_{i}$ a_i на максимальне з тих же чисел. Наприклад, якщо $a_{i} = 5$ a_i = 5 і його сусіди — $3$ і $2$ , то після мінімальної операції $a_{i}$ a_i стане $2$ . Якщо ж виконати максимальну операцію, $a_{i}$ a_i залишиться $5$ .

Для кожного $x$ від $1$ до $m$ знайдіть мінімальну кількість хвилин, необхідних, щоб усі числа стали рівними $x$ , або визначте, що це неможливо.

Вхідні дані

Перша строка містить два цілих числа $n$ і $m$ ( $3 \leq n \leq 2 \cdot 1 0^{5}$ 3 \leq n \leq 2 \cdot 10^5, $1 \leq m \leq 2 \cdot 1 0^{5}$ 1 \leq m \leq 2 \cdot 10^5) — кількість чисел у колі та кількість чисел, для яких потрібно знайти відповіді.

Друга строка містить $n$ цілих чисел $a_{1}$ a_1, $a_{2}$ a_2, ..., $a_{n}$ a_n ( $1 \leq a_{i} \leq m$ 1 \leq a_i \leq m) — числа, розташовані по колу.

Вихідні дані

Виведіть $m$ цілих чисел. $i$ -е число повинно бути рівним мінімальній кількості хвилин, необхідних для того, щоб усі числа стали рівними $i$ , або $- 1$ , якщо це неможливо.

Приклади

Приклад 1

Примітка

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

Виконайте операцію min для $a_{6}$ a_6, вона стане $2$ .
Виконайте операцію max для $a_{4}$ a_4, вона стане $2$ .
Виконайте операцію max для $a_{3}$ a_3, вона стане $5$ .
Виконайте операцію min для $a_{2}$ a_2, вона стане $2$ .
Виконайте операцію min для $a_{3}$ a_3, вона стане $2$ .