题目描述

有一个博客，初始赞数为0，每个人都会浏览这篇博客，如果这个人期望的赞数大于博客的赞数，他就会赞这篇博客，如果小于这篇博客，就踩一下（博客赞数-1），相同就不操作。询问对于每个k，对于前1~k 的人按照一个顺序浏览，求一种顺序使得博客最后的赞数最大，输出这个最大的赞数。

输入格式

第一行一个整数n，表示人数
第二行n 个整数，第i 个数表示第i 个人的期望赞数ai

输出格式

输出前k 个人最大的赞数，k 从1~n 变化

样例1

输入

4
2 0 2 2

输出

1
1
2
2

样例2

输入

7
2 -3 -2 5 0 -3 1

输出

1
0
-1
0
1
1
2

数据范围

对于 30%的数据，1 <= n <= 100，-100 <= ai <= 100
对于 100%的数据，1 <= n <= 5 * 10 ^ 5，-5 * 10 ^ 5 <= ai <= 5 * 10 ^ 5

限制

4s

来源

Codeforce773E
CWOI新高二专题测试八