g6-07914. 打家劫舍·首尾约束 未做

一条街上有 $n$ 间房（$n\ge 2$），第 $i$ 间房里有 $a_i$ 元现金。规定：第 $1$ 间必须偷，第 $n$ 间不能偷，且不能偷相邻的两间房。求最多能偷到多少钱。

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

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

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

输入 1

5
2 7 9 3 1

输出 1

11

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