← 返回题目列表

AtCoder · abc359_e

H. 水箱

中文机器翻译题面 查看原题

分数: 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:

  1. 增加值 A _ 0 by 1.
  2. 对于 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