众所周知,博客文章是 Codeforces 平台的重要组成部分。每篇博文都有一个随时间变化的全球特征——社区评级。新创建的博客文章的社区评级为 0。Codeforces 用户可以访问博客文章页面并对其进行评级,将其社区评级更改为 +1 或 -1。
考虑以下 Codeforces 用户行为模型。第 i 个用户有自己的估计博客文章评级,用整数 ai 表示。当用户访问博客文章页面时,他会将估计的博客文章评级与其社区评级进行比较。如果他的估计评分较高,他会为博客文章评分 +1(因此,博客文章的社区评分增加 1)。如果他的估计评分较低,他会将博客文章评分为 -1(将其社区评分降低 1)。如果估计评分和社区评分相等,则用户根本不会对博客文章进行评分(在这种情况下,我们会说用户对博客文章的评分为 0)。无论如何,在此过程之后,用户将关闭博客文章页面,并且再也不会打开它。
考虑一篇新创建的博客文章,其初始社区评分为 0。对于 n 个 Codeforces 用户(编号从 1 到 n)中的每一个,他的估计博客文章评分 ai 是已知的。
对于从 1 到 n(含)的每个 k,提出以下问题。让索引从 1 到 k 的用户按某种顺序访问博客文章页面,对博客文章进行评分并关闭页面。每个用户仅在前一个用户关闭博客文章后才打开该博客文章。在这 k 次访问之后,博客文章的最大可能社区评级是多少?
输入
第一行包含一个整数 n (1 ≤ n ≤ 5·105) — Codeforces 用户数量。
第二行包含 n 个整数 a1, a2, ..., an ( - 5·105 ≤ ai ≤ 5·105) - 按从 1 到 n 的顺序估计用户的博客文章评分。
输出
对于从 1 到 n 的每个 k,输出一个整数,该整数等于指数从 1 到 k 的用户按某种顺序访问博客文章页面、对博客文章进行评分并关闭页面后该博客文章的最大可能社区评分。
示例
输入 #1
4 2 0 2 2
输出 #1
1 1 2 2
输入 #2
7 2 -3 -2 5 0 -3 1
输出 #2
1 0 -1 0 1 1 2