В столице Берляндии есть n многоэтажных домов. Архитектор, который застраивал столицу, был человеком очень творческим, поэтому все дома были построены в один ряд.
Пронумеруем все дома слева направо, начиная с единицы. Дом считается элитным, если количество этажей в нем строго больше, чем во всех домах с большими номерами. Иными словами, дом элитный, если количество этажей в нем строго больше, чем во всех домах, которые расположены правее, чем он. В данной задаче полагается, что высоты всех этажей во всех домах одинаковы.
Нового архитектора заинтересовали n вопросов, i-й из которых звучит так: «сколько этажей нужно достроить к i-му дому, чтобы он стал элитным?» (где i принимает все значения от 1 до n). Вам предстоит помочь ему справиться с этой задачей.
Заметим, что все вопросы независимы друг от друга — ответ на вопрос для дома i не влияет на другие ответы (то есть, этажи к домам на самом деле не достраиваются).
Выходные данные
Выведите n целых чисел a1, a2, ..., an, где число ai равно количеству этажей, которые необходимо достроить к дому номер i, чтобы он стал элитным. Если дом уже элитный и к нему достраивать ничего не нужно, тогда ai должно быть равно нулю.
Все дома нумеруются слева направо, начиная с единицы.