На время прочтения условия задачи рекомендуем забыть, что лето состоит из $$$92$$$ дней, а день — из $$$1440$$$ минут. Это Берляндия, там всё по-другому.

Монокарп — студент провинциального университета в Берляндии. Только что начались летние каникулы, которые продлятся в ближайшие $$$n$$$ дней. Монокарп давно мечтал поехать в столицу Берляндии, поэтому он выберет из этих дней один день $$$i$$$, в который он приедет в столицу и проведет весь остаток каникул там.

Столица Берляндии — не очень дешевый город, а у Монокарпа с собой $$$0$$$ берляндских долларов. Естественно, этого не хватит, чтобы походить по интересным местам и закупиться сувенирами. Поэтому в некоторые дни в столице Монокарп будет работать на фрилансе (он не хочет работать у себя в городе, он и так весь учебный год выполнял задания по учебе).

Формально, в $$$i$$$-й день каникул у Монокарпа будет $$$a_i$$$ свободных минут, которые он потратит либо на работу, либо на отдых и покупку сувениров. Если у Монокарпа на начало $$$i$$$-го дня не меньше $$$a_i$$$ долларов, то он в этот день будет тратить их на отдых и сувениры со скоростью $$$1$$$ доллар в минуту, то есть за этот день он потратит $$$a_i$$$ долларов. Иначе он будет тратить это время на работу, зарабатывая $$$1$$$ доллар в минуту, то есть за этот день он заработает $$$a_i$$$ долларов. Обратите внимание, что Монокарп принимает решение на полный день; он никогда не зарабатывает и тратит в один и тот же день.

Ваша задача — для каждого количества дней $$$k$$$ от $$$1$$$ до $$$n$$$ определить, сколько долларов останется у Монокарпа после последнего дня каникул, если он пробудет в столице ровно $$$k$$$ дней (то есть приедет в столицу в день $$$(n-k+1)$$$).