【动态规划3】前缀和问题

题面描述：

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，要求你计算并输出每个前缀的和，即求出：

题目描述：

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，要求你计算并输出每个前缀的和，即求出：

其中， $1 \leq i \leq n$，即对于序列的每个前缀，输出其对应的和。

输入格式：

• 第一行输入一个整数 $n$（ $1 \leq n \leq 10^5$ ），表示序列的长度。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（ $1 \leq a_i \leq 10^4$ ），表示给定的整数序列。

输出格式：

• 输出 $n$ 行，每行输出一个整数 $S_i$，表示序列的第 $i$ 个前缀的和。

示例

输入：

5
1 2 3 4 5

输出：

1
3
6
10
15