题目描述

教具仓库与 $n$ 个班组有固定的交接顺序：第 1 个班组先来，第 2 个班组随后，一直到第 $n$ 个班组。每个班组来时与仓库做一次交接，交接量记为 $a_i$：$a_i > 0$ 表示该班组向仓库存入 $a_i$ 件教具，$a_i < 0$ 表示从仓库取走 $-a_i$ 件，$a_i = 0$ 表示该班组本次不交接。

仓库有一条硬规矩：任意时刻库存不能为负，取走时若库存不足就无法完成。因此，如果交接是从第 $i$ 个班组才开始的（前面的第 $1 \sim i-1$ 个班组都跳过），老师需要在这场交接开始之前预先备好若干件教具放在仓库里。

老师想做一个盘点：对每个 $i = 1, 2, \dots, n$，分别计算"从第 $i$ 个班组开始交接"所需的最少预存量。预存发生在从第 $i$ 个班组开始的这场交接之前，且第 $i$ 个班组本身的这次交接也要满足库存不为负。

输入格式

从文件 stock.in 中读入数据。

第一行一个正整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻两个整数之间用一个空格隔开。

输出格式

输出到文件 stock.out 中。

一行 $n$ 个整数，第 $i$ 个整数表示从第 $i$ 个班组开始交接所需的最少预存量，相邻两个整数之间用一个空格隔开。

数据范围

对于所有测试数据，保证：$1 \le n \le 10^5$，$|a_i| \le 10^6$。

特殊性质 A：每个班组的交接量都为负（即每个班组都在取走教具）。

特殊性质 B：恰好有一个班组的交接量为负，其余班组的交接量都非负。

4
3 -5 2 -4

4 7 2 4

3
2 3 4

0 0 0

样例解释

样例 1：从第 1 个班组开始，交接后库存依次为 $3, -2, 0, -4$，最低跌到 $-4$，需要预存 $4$ 件。从第 2 个班组开始，库存依次为 $-5, -3, -7$，最低 $-7$，需要预存 $7$ 件。从第 3 个班组开始，库存依次为 $2, -2$，需要预存 $2$ 件。从第 4 个班组开始，库存为 $-4$，需要预存 $4$ 件。

样例 2：每个班组都在存入，无论从哪个班组开始，库存只增不减，任何一场都不需要预存。