小 CCC 正在安排考场座位。
这里有一排 nnn 个座位，每个座位有一个舒适度 aia_iai，
如果一个座位最后有人就坐，就有 aia_iai 的收益。
小 CCC 按照如下原则安排座位：
可以撤去最右边连续 kkk 个座位， kkk 可以取 0,1,2,...,n0, 1, 2, ... ,n0,1,2,...,n。
为了防止作弊，不能有两个人相邻就坐。
为了提高利用率，不能有两个相邻的座位都无人就坐。
现在他想知道所有可能的安排方案中，总收益最大值是多少。
第一行一个整数 nnn。
第二行 nnn 个整数 a1,a2,...,ana_1, a_2, ... ,a_na1,a2,...,an。
一行一个整数，表示所有可能的安排方案中总收益的最大值。
10 9 -5 1 1 6 7 9 -6 9 -8
34
对于所有数据，保证 1≤n≤5×1041 \leq n \leq 5 \times 10^41≤n≤5×104，∣ai∣≤109|a_i| \leq 10^9∣ai∣≤109。