题目描述

古月现在有 $n$ 颗糖果，其中第 $i$ 颗糖果甜度为 $a_i$。古月从第 1 颗糖果开始试吃，按照序号依次吃下去。每颗糖果她可以选择吃或不吃，若她选择不吃，则试吃过程结束。古月现在想知道她能吃到的糖果甜度和最高为多少。

输入

第一行一个正整数 $n$。 第二行一共 $n$ 个整数，其中第 $i$ 颗糖果的甜度为 $a_i$。

输出

一个整数，表示古月能吃到的糖果最高甜度和。

样例

6
1 2 -3 6 -1 2

7

数据范围

• $n\le10^6$
• $\left\vert a_i\right\vert\le10^8$，其中 $i\in[1,n]$