不相邻奖励

难度：T2

【知识点：一维动态规划】

前置知识：数组、循环、状态与转移。

题目描述

一排共有 $n$ 个位置，第 $i$ 个位置的奖励为非负整数 $a_i$。可以选择任意一些位置，但相邻的两个位置不能同时选。求可得到的最大总奖励。可以一个位置都不选，不要求输出具体位置。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数 $a_1,\ldots,a_n$。

输出格式

一行一个整数，表示题目所求的最优总值。

样例输入

4
2 7 4 9

样例输出

16

样例解释

取第 $2,4$ 个位置，奖励 $7+9=16$。

数据范围

$1\le n\le100000$，$0\le a_i\le10^9$。