U264950 3D打印

Homura 正在使用3D打印机打印一排圆柱体。 将这些圆柱体从左往右依次编号为 $1$ 到 $n$，其需要打印的高度依次为 $h_{1}h_{2}\cdots h_{n}$，则3D打印机的工作流程如下： 1. 初始状态下所有圆柱体已打印高度为 $0$； 2. 将打印头移动到高度 $1$ 的位置； 3. 将打印头移动到编号为 $1$ 的圆柱体的位置； 4. 若当前圆柱体已打印高度小于需要打印的高度，则消耗 $1$ 单位材料使其已打印高度增加 $1$（即增加到当前打印头高度）； 5. 将打印头向右移动到编号加 $1$ 的圆柱体的位置，重复步骤 $4$，直到打印头移动到编号为 $n$ 的圆柱体的位置； 6. 将打印头向上移动高度 $1$，重复步骤 $3$ 到步骤 $5$，直到所有圆柱体已打印高度都等于需要打印的高度。 现在，Homura想知道，对于编号 $1$ 到 $n$ 的每个圆柱体，当其打印完成（即已打印高度等于需要打印的高度）时，打印机消耗了多少单位的材料。

输入数据的第一行包含一个整数 $n$ ($1\le n\le 10^6$)，n的含义见题目描述。 第二行包含 $n$ 个正整数 $h_{1}h_{2}\cdots h_{n}$ ($1\le h_{i}\le 10^9$)，$h_{i}$ 的含义见题目描述。

输出 $n$ 行，其中第 $i$ 行包含一个正整数，表示编号为 $i$ 的圆柱体打印完成时，打印机消耗的材料数量。

样例中各圆柱体打印完成时，打印机消耗的材料如下图所示。