U549625 小苯的区间和疑惑

帅气的大白熊这天向小苯提出了一个问题，他给了小苯一个长度为 $n$ 的数组 $a$ 。 他想知道，对于所有 $1 \leq i \leq n$ 的下标 $i$ ，都从数组中选择一段连续的区间 $[l, r]$ 使得 $l \leq i \leq r$ ，即选择一个包含 $i$ 的区间的话，这段区间和最大是几？ 请聪明的你帮帮小苯解答吧。

输入包含两行。 第一行一个正整数 $n (1 \leq n \leq 2\times10^5)$。 第二行 $n$ 个整数 $a_i (-10 ^9 \leq a_i \leq 10^9)$，表示这个数组。

输出包含一行 $n$ 个整数。 其中第 $i$ 个整数代表，选择一段包含 $a_i$ 的区间，这段区间的最大和。

### **样例解释1** $i = 1$ ，选择 $[1, 3]$，结果是： $1 + (-2) + 3 = 2$。是最优解。 $i = 2$ ，选择 $[1, 3]$ $i = 3$ ，选择 $[3, 3]$ $i = 4$ ，选择 $[3, 4]$