题目描述

有 \(n\) 个数排成一排，从 \(n\) 个数中任取若干个数，取数规则为每次取相邻的 \(2\) 个数，不能取 \(1\) 个，也不能取多于 \(2\) 个连续的数，找一种取法，使取到数的和为最大。

例如：\(n=6\)，\(6\)个数为：\(13 \ 2 \ 17 \ 14 \ 8 \ 16\)，取数方法有：

\(①\) \(13 \ 2 \ 14 \ 8\)，取得的数字和为 \(37\)；

\(②\) \(13 \ 2 \ 8 \ 16\) ，取得的数字和为 \(39\)；

\(③\) \( 2 \ 17 \ 8 \ 16\)，取得的数字和为 \(43\)；

\(④\) \(17 \ 14\)，取得的数字和为 \(31\)；

其中和最大的为\(43\)。

格式

输入格式

第 \(1\) 行一个整数\(n\)；

第 \(2\) 行 \(n\) 个整数 \(x[i]\)，表示给定的数列。

输出格式

包含一个整数，即合理取法中最大的和。

样例1

样例输入1

6
13 2 17 14 8 16

样例输出1

43

限制

\(100\%\)的数据：\(2≤n≤1000，1≤x[i]≤10000\)。