В Байтсбурге вводится новая система оплаты общественного транспорта. Теперь будет единая карта для поездок на всем транспорте. При каждой поездке пассажир прикладывает карту к считывателю, и с него списывается сумма в соответствии с тарифом.
Тариф устроен следующим способом. Есть три вида билетов:
Уточним, что билет на x минут, активированный во время t, действует на поездки, стартовое время которых находится в диапазоне от t до t + x - 1, включительно. Считайте, что каждая поездка занимает ровно одну минуту.
Чтобы пассажиру было проще, тариф выбирается автоматически: при совершении каждой поездки система анализирует все прошедшие поездки и текущую и выбирает набор билетов на эти поездки с минимальной суммарной стоимостью. Пусть минимальная стоимость, за которую можно совершить поездки с первой по текущую, равна a, а сумма, списанная с пассажира за все предыдущие поездки, равна b. Тогда система списывает с пассажира разницу a - b.
Вам предстоит написать программу, которая по данным о времени совершенных пассажиром поездок рассчитает сумму, которую нужно с него снять после каждой из них.
В первой строке ввода содержится число n (1 ≤ n ≤ 105) — число поездок, которые сделал пассажир.
В каждой из следующих n строк содержится время начала поездки ti (0 ≤ ti ≤ 109), измеренное в минутах от момента запуска системы. Все ti различны, заданы в порядке возрастания, т. е. ti + 1 > ti для всех 1 ≤ i < n.
Выведите n чисел. Для каждой поездки выведите сумму, которую нужно снять с карты пассажира.
3
10
20
30
20
20
10
10
13
45
46
60
103
115
126
150
256
516
20
20
10
0
20
0
0
20
20
10
В первом примере система работает следующим образом: первую и вторую поездку дешевле всего оплатить двумя билетами на одну поездку, поэтому с пассажира снимается по 20 рублей, после третьей поездки система понимает, что дешевле было бы купить билет на 90 минут. Этот билет стоит 50 рублей, а пассажир к этому времени уже заплатил 40 рублей, таким образом с него нужно дополнительно взять 10 рублей.
| 8VC Venture Cup 2017 - Final Round |
|---|
| Закончено |
