Migrated from Lutece 3242 Summer Pockets REFLECTION BLUE

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

本题为 Summer Pockets 的加强版本

是时候成为鸟白岛上首屈一指的岛可梦大师了！

羽依里正在进行岛可梦大乱斗，对方一共有 $n$ 只岛可梦，第 $i$ 只岛可梦的血量为 $a_i$。

羽依里的目标是在一回合内将所有对方岛可梦全部击败，若某个时刻某只岛可梦的血量降到了 $0$，则认为该岛可梦被击败，并将其移出战斗。

虽然羽依里只有一只岛可梦—— 稻荷，但它的实力绝对不容小觑，稻荷 共有以下两种技能：

1. 对任意一只对方岛可梦造成 $1$ 点伤害，这个技能的目标可以由羽依里任意指定。
2. 对所有对方岛可梦造成 $1$ 点伤害，如果这个技能杀死了至少一只对方岛可梦，则自动再次释放该技能。

不幸的是现在 稻荷 只能释放技能2至多一次了，请帮助羽依里求出在这种情况下最少要释放多少次技能1才能在一回合将所有对方岛可梦全部击败。

这一次，你需要对 $\{a_i\}$ 的所有前缀均计算答案，具体地：

• 对于 $k=1,2,\dots,n$，假设只有 $\{a_i\}$ 中的前 $k$ 只岛可梦时，计算最少要释放的技能1的次数。
• 不同的 $k$ 对应的询问之间相互独立。

Input

输入的第一行包括一个正整数 $n$，表示对方岛可梦的数量。

第二行包括一个长为 $n$ 的序列 $\{a_i\}$，表示对方岛可梦的血量。

Output

输出一行共 $n$ 个整数，分别表示 $k=1,2,\dots,n$ 时最少要释放的技能1的次数。

Samples

3
3 1 2

2 1 0

6
4 1 5 4 1 1

3 2 4 4 4 4

Constraints

$1\le n\le 2\times 10^5,1\le a_i\le n$