思路：搜索

定义$dfs(l,r,sum)$表示当前左边界为$l$（不包含），有边界为$r$（不包含），总计和为$sum$的情况。

则下一步考虑向左或者向右搜索，即$dfs(l-1,r,sum+a[l])$或者$dfs(l,r+1,sum+a[r])$。

当然，$l$和$r$不能超过数组的左右边界。

由于$1\le a_i\le 10^9$，且每次均只能加比自己大的数，因此最多仅能扩展30次($2^{30}=1073741824$)

题目内容

给出一个长度为$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