E. Оценивание блогпостов
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, важной составляющей платформы Codeforces являются блогпосты. Каждый блогпост имеет глобальную характеристику, изменяющуюся во времени — оценку блогпоста сообществом. Когда блогпост только создан, его оценка сообществом равна 0. Пользователи Codeforces имеют право заходить на страницу блогпоста и оценивать его, изменяя его оценку сообществом на +1 или -1.

Рассмотрим следующую модель поведения пользователей Codeforces. i-й пользователь имеет собственную оценку блогпоста, выраженную некоторым целым числом ai. Когда пользователь заходит на страницу с блогпостом, он сравнивает собственную оценку блогпоста с текущей оценкой блогпоста сообществом. Если собственная оценка оказалась выше, пользователь ставит блогпосту оценку +1 (таким образом, оценка блогпоста сообществом увеличивается на 1). Если собственная оценка ниже, пользователь ставит блогпосту оценку -1 (понижая его оценку сообществом на 1). Если оценки совпали, пользователь не ставит блогпосту ни +1, ни -1 (мы будем говорить, что в таком случае пользователь поставил блогпосту оценку 0). В любом случае, после данной процедуры пользователь закрывает блогпост и больше никогда к нему не возвращается.

Рассмотрим некоторый только что созданный блогпост, исходная оценка которого сообществом равна 0. Про каждого из n пользователей Codeforces, пронумерованных от 1 до n, известна его собственная оценка данного блогпоста ai.

Для каждого k от 1 до n, включительно, требуется ответить на следующий вопрос. Пусть пользователи с индексами от 1 до k в некотором порядке откроют страницу с данным блогпостом, оценят его и закроют страницу. Каждый пользователь открывает блогпост только после того, как его закрыл предыдущий пользователь. Какую максимальную оценку сообществом может иметь данный блогпост по итогам этих k просмотров?

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

Первая строка содержит целое число n (1 ≤ n ≤ 5·105) — количество пользователей Codeforces.

Вторая строка содержит n целых чисел a1, a2, ..., an ( - 5·105 ≤ ai ≤ 5·105) — собственные оценки блогпоста пользователей в порядке от 1 до n.

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

Для каждого k от 1 до n выведите целое число, равное максимальной возможной оценке блогпоста сообществом после того, как пользователи с индексами от 1 до k в некотором порядке зайдут на страницу с блогпостом, оценят его и закроют страницу.

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