一排学生共 $n$ 个人在一起听课，分别坐在位置 $1,2,3...n$，每个人都有一个听课认真度 $a_i$，这时来了一个调皮的插班生，他会影响别人听课。具体来说，距离他 $dis$ 的学生（距离即两个人位置之差的绝对值），听课认真度将减少 $n - dis$，注意，一位学生的听课认真度最低不会低于 0。总共有 $n$ 个座位供插班生选择，被占领座位的学生将被踢出班级，其他人的座位不变，但听课认真度会减少。现在想知道，如果插班生坐在了位置 $1,2,3,4...n$，所有学生的听课认真度之和分别是多少。（插班生没有听课认真度）

输入格式

第一行输入一个正整数 $n$， 表示学生的个数。

接下来一行输入 $n$ 个正整数，表示每个学生的听课认真度。

输出格式

输出 $n$ 个正整数，其中第 $i$ 个正整数表示当插班生坐在位置 $i$ 时，所有学生的听课认真度之和。

样例 #1

样例输入 #1

5
10 1 10 10 10

样例输出 #1

24 27 20 20 22

样例 #2

样例输入 #2

5
3 1 4 1 5

样例输出 #2

5 3 2 2 3

数据范围及提示

【样例解释 #1】

当插班生坐在位置 1 时，第一个学生被踢出，我们可以认为第一个位置的听课认真度由 10 变为 0。她离第二个学生的距离 $dis = |1-2| = 1$，即第二个学生的听课认真度会减少 $n - dis = 5 - 1 = 4$。但是第二个学生的听课认真度不会小于 0，所以他的听课认真度减少为 0。第三个学生距离为 2，认真度减少 5-2=3，以此类推。此时每个位置的听课认真度为 [0,0,7,8,9]，求和得到 24。

当插班生坐在位置 2 时，每个位置的听课认真度为 [6,0,6,7,8]，求和得到 27。

当插班生坐在位置 3 时，每个位置的听课认真度为 [7,0,0,6,7]，求和得到 20。

【数据范围】