题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统。 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组， 计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

输入格式

第一行是一个正整数N，表示了房子总数量。(N≤100) 第二行是用空格分开的N个非负整数，每个房间的现金数额。

输出格式

一个整数，为能够偷窃到的最高金额。

样例

输入样例 1

4
1 2 3 1

输出样例 1

4

输入样例 2

2
2 3

输出样例 2

3

输入样例 3

5
2 7 9 3 1

输出样例 3

12