题目描述

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

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

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

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

当顾客数目 $x$ 小于距离活动商店的距离y的话，不会有任何一个顾客去参加活动，否则，举办活动的商店就能够从未举办活动的商店前的顾客中吸引到 $max(⌊x/y⌋,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≤n≤3000$

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

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

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