该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

阁中帝子今何在？槛外长江空自流

题目描述

小 L 看到孤雁成功（或者失败）找到同伴以后，随着江水想到了滚滚而去的历史。历史的长河中闪耀着 $n$ 个璀璨的瞬间，每个瞬间都有其独特的“奇怪值” $v_i$，其对应的“历史价值”为 $-v_i$。

这些瞬间是按照时间顺序依次排开的。小 L 想要从中挑选出一些瞬间记录在自己的笔记里。但是，历史的感悟是需要时间的：如果小 L 记录了第 $i$ 个瞬间，为了平复澎湃的心情，他就不能记录紧挨着它的两个瞬间（第 $i-1$ 个和第 $i+1$ 个瞬间；特别地，除非 $n = 1$，否则第一个瞬间和最后一个瞬间也算作相邻）。

小 L 想知道，在不记录相邻瞬间的前提下，他能收集到的历史价值总和最大是多少？

输入格式

本题有多组数据，请读入至 EOF 结束。

输入共两行。

第一行包含一个正整数 $n$，表示历史瞬间的总数。

第二行包含 $n$ 个整数 $v_1, v_2, \ldots, v_n$，表示每个瞬间的奇怪值。

输出格式

输出一行一个整数，表示小 L 能收集到的最大价值总和。

输入输出样例

8
18 -1 -2 6 -3 -4 2 0
6
60 -99 -97 10 -69 46
10
0 0 0 0 0 0 0 0 0 0
6
0 9962 951 -10913 0 0

6
168
0
10913

说明/提示

数据规模与约定

1. $1 \le n \le 10^5$
2. $|v_i| \le 10^9$
3. 输入的数字个数不超过 $10^5$