题目内容

给出一个长度为$n$的数组$a_1,a_2,...,a_n$，假如你从$x$点出发（初始区间为$[x,x]$，初始价值为$a_x$），每到

达一个点就把这个点加入到区间内并获得当前点的价值，每次能将当前所拥有的区间向右或者向左扩展

一个（不能超过边界），且被拓展的位置的值一定要大于当前所拥有的价值之和。

输出对于起点$x=1,2,...,n$，答案分别是多少。

输入描述

第一行正整数$n$，表示数组的长度。

接下来一行$n$个正整数代表$a_1,a_2,...,a_n$。

$1≤ n≤ 10^5$，$1≤ a_i≤ 10^9$

输出描述

输出一行$n$个数字代表答案。

示例 1

输入

3
2 1 4

输出

2 7 4

说明

从$1,3$出发只能在自己$2$出发先变成$[1,2]$，再变成$[2,3]$

示例2

输入

5
2 3 6 1 4

输出

11 9 6 11 4