题目描述

给定 n 个整数 $a[1..n]$，选择其中若干个数，要求不能选择相邻位置，求选出元素的最大和,至少选择一个数。

输入格式

第一行一个数字N，表示序列长度。

第二行，N个数字表示该整数序列。

输出格式

一行，表示该问题的答案。

输入输出样例 #1

5
2 7 9 3 1

12

说明/提示

$1 \leq N \leq 10^6，-10^5 \leq a_i \leq 10^5$

样例1解释

选择$2,9,1$三个数字最大和为12。