403048: GYM100981 F Карлсон

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

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

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

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

В первой строке входных данных содержатся два целых числа n и h (2 ≤ n ≤ 106, 1 ≤ h ≤ 109) — номер этажа, на котором живёт Малыш, и рост Карлсона соответственно. В следующей строке записаны целые числа h1, h2, ..., hn - 1 (1 ≤ hi ≤ 109), i-е из которых соответствует росту друга Карлсона, проживающему на i-м этаже.

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

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

ПримерыВходные данные
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 

加入题单

上一题 下一题 算法标签: