故事

有一个长长的水缸，水缸里等距地摆放着不同高度的木板。光头强想知道当水从水箱的一端倒入时，水到达由板隔开的每个部分的时间。

问题描述

给定一个长度为 $N$ 的正整数序列：$H=(H_1,H_2,\dotsc,H_N)$。

存在长度为 $N+1$ 的非负整数序列：$A=(A_0,A_1,\dots,A_N)$。最初，$A_0=A_1=\dots=A_N=0$。

重复执行以下操作:

• 步骤1.将 $A_0$ 的值增加 1。
• 步骤2.对 $i=1,2,\ldots,N$，依次执行以下操作:
  • 如果 $A_{i-1}>A_{i}$ 和 $A_{i-1}>H_{i}$，则将 $A_{i-1}$ 的值减少 1，并将 $A_{i}$ 的值增加 1。

对于每个 $i=1,2,\ldots,N$，找出首次 $A_i>0$ 时的操作次数。

数据规模

$1\leq N\leq2×10^5$

$1\leq H_i\leq10^9(1\leq i\leq N)$

所有输入值都是整数。

输入

输入来自标准输入，格式如下:

$N$

$H_1\ H_2\dots H_N$

输出

在一行中打印 $i=1,2,\ldots,N$ 的答案，用空格分隔。

5
3 1 4 1 5

4 5 13 14 26

前五个操作如下。

这里，每行对应于一个操作，最左边的列表示步骤 1，其他列表示步骤 2。

在该图中，在第 $4$ 次操作后首次 $A_1>0$，在第 $5$ 次操作后首次 $A_2>0$。

类似地，$A_3,A_4,A_5$ 的答案分别是 13、14、26。

因此，您应该打印 4 5 13 14 26。

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

请注意，要输出的值可能不在 $32$ 位整数范围内。

15
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632

749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373