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

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

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

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