水槽

题目描述

有一个很长的水槽,等间隔地放置着高度各不相同的挡板。高桥君想知道,从水槽的一端注水时,水到达被挡板分隔开的每个区段的时间。

给定一个长度为 $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$ 的值增加 $1$。
2. 按 $i=1,2,\ldots,N$ 的顺序,依次执行以下操作:
   • 如果 $A_{i-1}\gt A_i$ 且 $A_{i-1}\gt H_i$,则将 $A_{i-1}$ 的值减 $1$,并把 $A_i$ 的值增加 $1$。

对每个 $i=1,2,\ldots,N$,求 $A_i\gt 0$ 首次成立时,已经执行了多少次操作。

输入格式

输入按以下格式从标准输入给出:

$N$
$H_1$ $H_2$ $\dotsc$ $H_N$

输出格式

在一行内,用空格分隔输出 $i=1,2,\ldots,N$ 的答案。

样例

5
3 1 4 1 5

4 5 13 14 26

前 5 次操作后 $A$ 的状态依次如下(每次操作都先执行步骤 1,再执行步骤 2):

(1,0,0,0,0,0)
(2,0,0,0,0,0)
(3,0,0,0,0,0)
(3,1,0,0,0,0)
(3,1,1,0,0,0)

由此可知,$A_1\gt 0$ 在第 4 次操作后首次成立,$A_2\gt 0$ 在第 5 次操作后首次成立。

类似地,$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

数据范围

• $1 \le N \le 2\times10^5$
• $1 \le H_i \le 10^9\ (1 \le i \le N)$
• 输入均为整数。