g6-07911. 打家劫舍 II（环形） 未做

$n$ 间房围成一圈，第 $i$ 间房里有 $a_i$ 元现金。小偷不能偷相邻的两间房（第 $1$ 间和第 $n$ 间也相邻）。求最多能偷到多少钱。

第一行一个整数 $n$（$1\le n\le 10^5$）。

第二行 $n$ 个整数 $a_1,\dots ,a_n$（$1\le a_i\le 10^4$）。

一行一个整数，表示最多能偷到的金额。

输入 1

3
2 3 2

输出 1

3

输入 2

4
1 2 3 1

输出 2

4

对于所有数据，$1\le n\le 10^5$，$1\le a_i\le 10^4$。