分数: 500 点
故事
有一个长长的水箱,等间隔放置着不同高度的木板。 高桥想知道当水从水箱一端倒出时,水到达由木板隔开的每个部分的时间。
问题陈述
给定一个长度为正整数的序列 N: H=(H _ 1,H _ 2,\dotsc,H _ N).
存在一个长度为非负整数的序列 N+1: A=(A _ 0,A _ 1,\dotsc,A _ N)。最初, A _ 0=A _ 1=\dotsb=A _ N=0.
重复执行以下操作 A:
- 增加值 A _ 0 by 1.
- 对于 i=1,2,\ldots,N 按此顺序执行以下操作:
- If A _ {i-1}\gt A _ i 和 A _ {i-1}\gt H _ i,减少值 A _ {i-1} 加 1 并增加 A _ i by 1.
对于每个 i=1,2,\ldots,N,查找之前的操作次数 A _ i>0 首次成立。
约束
- 1\leq N\leq2\times10 ^ 5
- 1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N H _ 1 H _ 2 \dotsc H _ N
输出
打印以下问题的答案 i=1,2,\ldots,N 位于一行中,以空格分隔。
示例输入 1
5 3 1 4 1 5
示例输出 1
4 5 13 14 26
前五个操作如下。
这里,每一行对应一个操作,最左边的列代表步骤 1,其他列代表步骤 2。

从这张图中, A _ 1\gt0 在第4次操作后首次成立,并且 A _ 2\gt0 在第 5 次操作后首次成立。
同样,答案 A _ 3, A _ 4, A _ 5 是 13, 14, 26。
因此,您应该打印 4 5 13 14 26.
示例输入 2
6 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 2
1000000001 2000000001 3000000001 4000000001 5000000001 6000000001
请注意,要输出的值可能不适合 32位整数。
示例输入 3
15 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632
示例输出 3
749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373