wwx 的电磁干扰

题目描述

wwx 的手机网络最近越来越慢了，他仔细观察以后发现原来是城市里被人搭建了总共 $n$ 台窃取流量的设备！

wwx 发现这 $n$ 台设备搭建的位置是一条直线贯穿整个城市，所以可以简单的将这 $n$ 台设备依次编号为 $1,2,3 \dots n$，它们之间的距离均匀分布，可以简单的将它们的编号看作是在直线上的位置，每台设备都有一个工作强度 $a_i$，代表了这台机器能够窃取流量的强度。

在 wwx 上报这些信息以后，网络监管局闪送了一台电磁干扰器给 wwx ，希望 wwx 先抢修一下城市的网络，等到后期抓到这个人以后再统一拆除所有设备。

抢修方案是这样的： wwx 可以选择任意一台设备将它拆除，并且在它所在的位置安装电磁干扰器，这台电磁干扰器会影响所有的设备，如果电磁干扰器设置在位置 $x$ 处，那么对于第 $i$ 台设备的距离即为 $dis = |x - i|$，会使得这台设备的工作强度降低 $n - dis$。

当然，一台设备的工作强度不会低于 $0$。

现在 wwx 想要知道他在每一个位置设置电磁干扰器时，所有的窃取设备工作强度之和分别是多少。

输入格式

第一行输入一个正整数 $n$， 表示网络窃取设备的个数。

接下来一行输入 $n$ 个正整数 $a_i$，表示每台设备的工作强度

输出格式

输出 $n$ 个数字，第 $i$ 个数字表示 wwx 拆除第 $i$ 台设备并设置电磁干扰器时，所有设备工作强度之和。

数据范围

测试点

$n \leq$

$a_i$

1-2

1000

$1 \leq a_i \leq 2*10^5$

3-6

$10^5$

$n \leq a_i \leq 2*10^5$

7-10

$1 \leq a_i \leq 2*10^5$

样例输入

5
10 1 10 10 10

样例输出

24 27 20 20 22

样例解释

wwx 拆除第 $1$ 台设备并设置电磁干扰器时，五台设备的工作强度分别为 $0,0,7,8,9$，所以总和为 $24$
wwx 拆除第 $2$ 台设备并设置电磁干扰器时，五台设备的工作强度分别为 $6,0,6,7,8$，所以总和为 $27$
wwx 拆除第 $3$ 台设备并设置电磁干扰器时，五台设备的工作强度分别为 $7,0,0,6,7$，所以总和为 $20$