g6-07913. 不相邻子序列最大和 未做

给定 $n$ 个整数（可能为负）。选出一个子序列，要求任意两个被选元素的下标不相邻。允许一个都不选（和为 $0$）。求最大和。

第一行一个整数 $n$（$1\le n\le 10^5$）。

第二行 $n$ 个整数 $a_i$（$-10^4\le a_i\le 10^4$）。

一行一个整数，表示最大和。

输入 1

4
-2 1 3 -1

输出 1

3

输入 2

3
-5 -2 -3

输出 2

0

对于所有数据，$1\le n\le 10^5$，$-10^4\le a_i\le 10^4$。