403048: GYM100981 F Карлсон

F. Карлсонограничение по времени на тест3 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Прошло 20 лет. Карлсон располнел и больше не летает. Малыш устроился на работу, стал топ-менеджером и теперь живёт в огромном доме на n-м этаже.

Карлсон решил пойти в гости к Малышу. Разумеется, пешком подниматься он не собирается, поэтому на первом этаже Карлсон заходит в лифт.

Кнопки в лифте расположены снизу вверх таким образом, что человек с ростом h может достать до любой кнопки, соответствующей этажу от 1 до h включительно. При этом на i-м этаже у Карлсона есть друг с ростом h_i, и его можно попросить нажать на любую кнопку, до которой он может дотянуться. Разумеется, чтобы попросить друга с i-го этажа нажать на кнопку, сначала нужно оказаться на этаже i. Карслон хочет добраться до Малыша, обратившись за помощью к минимально возможному количеству друзей.

К сожалению, со временем у Карлсона также испортился характер, поэтому иногда он ссорится со своими друзьями, но не более чем с одним другом одновременно. Карлсон хочет для каждого i определить минимальное число друзей, к которым придётся обратиться за помощью, если он поссорится с другом номер i и не сможет обращаться к нему с просьбой нажать на кнопку.

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

В первой строке входных данных содержатся два целых числа n и h (2 ≤ n ≤ 10⁶, 1 ≤ h ≤ 10⁹) — номер этажа, на котором живёт Малыш, и рост Карлсона соответственно. В следующей строке записаны целые числа h₁, h₂, ..., h_n - 1 (1 ≤ h_i ≤ 10⁹), i-е из которых соответствует росту друга Карлсона, проживающему на i-м этаже.

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

Выведите n - 1 число ans₁, ans₂, ..., ans_n - 1, где ans_i равно минимальному количеству друзей, которых придётся попросить помочь, если Карлсон поссорится с другом, проживающим на i-м этаже. Если, поссорившись с i-м другом, Карлсон не сможет добраться до Малыша, то выведите -1 вместо соответствующего значения ans_i.

ПримерыВходные данные

2 2
2

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

0 

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

2 2
2

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

0 

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

3 2
2 3

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

1 -1 

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

8 5
5 8 6 6 7 12 14

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

1 2 1 1 1 1 1 

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

3 1
1 2

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

-1 -1