Вагоны новой кольцевой железной дороги было предложено расписать N дизайнерам. Каждый дизайнер выбирал для своей раскраски полосу длиной li, начинающуюся от начала вагона и гарантированно помещающуюся на вагоне. Тем самым какие-то работы были полностью закрашены, а какие-то всё же были видны хотя бы частично. Вам дана последовательность перекраски. После завершения работы каждого дизайнера выведите одно число — количество различных работ, элементы которых видны на момент завершения.
Желательно c++

Формат ввода

В первой строке дано количество дизайнеров 1 ≤ N ≤ 105 Во второй строке через пробел даны N целых чисел 1 ≤ li ≤ 109 – длины полос.

Формат вывода

Выведите N чисел через пробел. i-е из этих чисел соответствует количеству различных работ, элементы которых видны после завершения работы i-го дизайнера.

Примеры:

Ввод

3

1 3 2

Вывод

1

1

2.

a6+a9=20

a1+5d+a1+8d=20

2a1+13d=20

a14=a1+13d

s(n)=(a1+a(n))*n/2

s(14)=(a1+a14)*14/2

s(14)=20*14/2

s14=140

из записи функции непонятно 1 в знаменателе, или нет. рассмотрим, что она не в знаменателе:

y=(2/x)+1

y ' =-2/x^2

в точке x=0- функция не определенна

y ' < 0   для всех x, кроме x=0, то есть на интервалах (-бескон.; 0) и (0; + функция убываеи