题目描述

游戏地图上有 $N$ 个连续房间，第 $i$ 个房间中有 $a_i$ 枚金币。安全系统规定：如果连续两个房间都被取走金币，就会立刻触发警报。

霸王龙可以选择任意一些互不相邻的房间，请计算最多能取得多少枚金币。

输入格式

第一行包含整数 $N$，满足 $1\le N\le2\times10^5$。第二行输入 $N$ 个非负整数 $a_i$，满足 $0\le a_i\le10^9$。

输出格式

输出在不选择相邻房间的条件下能够取得的最大金币数。

5
2 7 9 3 1

12