题目说明：

有一条商店街，商店街开了 $n$ 家店，相邻商店之间的距离为1。

现在每一家店门前都各自有 $a_i$ 位顾客准备购物，小核桃作为商店街的管理员，他准备在某一家商店举办购物活动。

当某一家商店举办活动时，首先该商店门前的顾客不会改去其他的商店，并且举办活动还会吸引来自其他商店的顾客，能够吸引到其他店的顾客数目，与其他店距离购物活动商店的距离和人数有关。

具体来说假设一个未举办活动的商店门前的顾客数目为x，距离活动商店 $y$ 个单位的话。

当顾客数目x小于距离活动商店的距离y的话，不会有任何一个顾客去参加活动，否则，举办活动的商店就能够从未举办活动的商店前的顾客中吸引到 $max(\lfloor x/y \rfloor,x\%y)$ 位顾客。

其中 $x\%y$ 表示 $x$ 整除 $y$ 的余数。

现在小核桃想要知道，假设他在第 $i$ 家商店举办活动，有多少顾客会来参加购物活动。

输入格式：

第一行输入一个正整数 $n$，表示商店街中开了 $n$ 家店。

接下来一行 $n$ 个正整数$a_i$表示每家店门前的顾客数。

输出格式：

输出一行 $n$ 个正整数，表示假设在第 $i$ 家商店举办活动，有多少顾客会来参加购物活动。

5
1 2 3 2 1

4 7 7 7 4

13
3277 3244 4063 2669 2770 4651 2557 4500 4743 3671 4907 3939 4286

14335 17726 18880 19746 20632 21129 22512 22846 23353 23329 22136 20759 16691

数据范围及约束：

对于30%的测试数据$1 \leq n \leq 3000$

对于另10%的测试数据$1 \leq n \leq 3 \times 10^4$且保证所有的$a_i$均相同。

对于另20%的测试数据$1 \leq n \leq 3 \times 10^4$且保证$a_i$的种类数不多于2种。

对于100%的测试数据，保证$1 \leq n,a_i \leq 3 \times 10^4$

大样例

T3sample