6075: 打家劫舍 II
[Creator : ]
Description
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
Input
一共两行。
第一行为一个整数 $n\ (1 \leq n \leq 10^6)$
第二行包括 $n$ 个整数。第 $i$ 个整数 $a_i\ (0≤a_i≤10^4)$ 表示第 $i$ 个房间的现金。
第一行为一个整数 $n\ (1 \leq n \leq 10^6)$
第二行包括 $n$ 个整数。第 $i$ 个整数 $a_i\ (0≤a_i≤10^4)$ 表示第 $i$ 个房间的现金。
Output
一共一行，包括一个数字，表示答案。
Sample 1 Input
3
2 3 2
Sample 1 Output
3
你不能先偷窃 $1$ 号房屋（金额 $= 2$），然后偷窃 $3$ 号房屋（金额 $= 2$）, 因为他们是相邻的。
Sample 2 Input
4
1 2 3 1
Sample 2 Output
4
你可以先偷窃 $1$ 号房屋（金额 $= 1$），然后偷窃 $3$ 号房屋（金额 $= 3$）。偷窃到的最高金额 $= 1 + 3 = 4$。
Sample 3 Input
10
43 4 4 1 26 29 24 44 52 12
Sample 3 Output
149