打家劫舍 II（环形街区）

题目描述

你是一名专业的小偷，计划偷窃一条环形街道上的房屋。街道上总共有 $n$ 间房屋，第 $i$ 间房屋中藏有金额 $a_i$。

由于房屋间的防盗系统是相互连通的，如果两间相邻的房屋在同一晚上被闯入，报警系统就会被触发。

与普通的直线街道不同，这条街道是首尾相连的环形：

• 第 1 间房屋与第 2 间房屋相邻；
• 第 $n$ 间房屋与第 $n-1$ 间房屋相邻；
• 同时，第 1 间房屋与第 $n$ 间房屋也相邻。

换句话说，你不能同时偷窃两间相邻的房屋，特别地，第 1 间和第 $n$ 间房屋也不能在同一晚上同时被偷。

请你计算，在不触发报警系统的前提下，一夜之间你能偷窃到的最高金额。

---

输入格式

• 第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示房屋数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 400$），表示每间房屋中的现金金额。

---

输出格式

输出一个整数，表示在不触发警报的前提下，能够偷窃到的最高金额。

---

示例

示例 1

输入：

3
2 3 2

输出：

3

解释：
房屋排列为一个环，金额分别为 [2, 3, 2]。
你不能同时偷窃第 1 间和第 3 间房屋。最优策略是只偷第 2 间房屋，获得金额 3。

---

示例 2

输入：

4
1 2 3 1

输出：

4

解释：
房屋金额为 [1, 2, 3, 1]，排列成环。
你不能同时偷窃第 1 间和第 4 间房屋。
一种最优方案是偷窃第 1 间和第 3 间房屋，获得金额 $1 + 3 = 4$。

---

数据范围

• $1 \leq n \leq 100$
• $0 \leq a_i \leq 400$