B. Элитные дома
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В столице Берляндии есть n многоэтажных домов. Архитектор, который застраивал столицу, был человеком очень творческим, поэтому все дома были построены в один ряд.

Пронумеруем все дома слева направо, начиная с единицы. Дом считается элитным, если количество этажей в нем строго больше, чем во всех домах с большими номерами. Иными словами, дом элитный, если количество этажей в нем строго больше, чем во всех домах, которые расположены правее, чем он. В данной задаче полагается, что высоты всех этажей во всех домах одинаковы.

Нового архитектора заинтересовали n вопросов, i-й из которых звучит так: «сколько этажей нужно достроить к i-му дому, чтобы он стал элитным?» (где i принимает все значения от 1 до n). Вам предстоит помочь ему справиться с этой задачей.

Заметим, что все вопросы независимы друг от друга — ответ на вопрос для дома i не влияет на другие ответы (то есть, этажи к домам на самом деле не достраиваются).

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

В первой строке входных данных записано единственное целое число n (1 ≤ n ≤ 105) — количество домов в столице Берляндии.

Во второй строке через пробел записаны n целых положительных чисел hi (1 ≤ hi ≤ 109), где hi равно количеству этажей в i-м доме.

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

Выведите n целых чисел a1, a2, ..., an, где число ai равно количеству этажей, которые необходимо достроить к дому номер i, чтобы он стал элитным. Если дом уже элитный и к нему достраивать ничего не нужно, тогда ai должно быть равно нулю.

Все дома нумеруются слева направо, начиная с единицы.

Примеры
Входные данные
5
1 2 3 1 2
Выходные данные
3 2 0 2 0
Входные данные
4
3 2 1 4
Выходные данные
2 3 4 0