轮休值守

修复完了，但哨兵需要轮休——不能一直站岗。

"轮休？"CC问。

"对。"你说，"$n$个哨兵排成一个环，每个哨兵站岗有一个疲劳值。相邻哨兵不能同时休息，求最小总疲劳。"

"不能同时？"

"对。"你说，"至少要有一个站岗——不能全休息。"

"最小？"

"对。"你说，"让站岗的哨兵总疲劳最小。"

"咋算？"

"分类。"你说，"第一个哨兵站岗或休息，两种情况分别DP。"

"DP？"

"对。"你说，"$dp[i][0/1]$表示第$i$个哨兵休息/站岗时的最小总疲劳。"

"转移？"

"如果$i$休息，$i-1$必须站岗。"你说，"如果$i$站岗，$i-1$可以休息或站岗。"

"第47个哨兵。"你说，"疲劳47——如果让他休息，前面的必须站岗。"

"选不选他？"

"看总和。"你说，"如果他的疲劳很高，让他休息，让 fatigue 低的站岗。"

"像排班？"

"对。"你说，"像排班——有人上班，有人休息，轮流来。"

"公平？"

"对。"你说，"每个人都休息，每个人都站岗。"

"如果不公平？"

"有人累垮。"你说，"一直站岗，受不了。"

"累垮？"

"对。"你说，"所以要轮休——轮着来，大家都轻松。"

CC看着那些哨兵——像一排灯，像一排队，像某种需要轮换的东西。

"谁站？"她问。

"算。"你说，"DP算出最优方案。"

"能算出来？"

"能。"你说，"$O(n)$。"

Echo把轮休表投射出来——站岗的亮，休息的暗，像昼夜交替。

"以前我不休息。"她说，"现在……知道累了。"

"因为你在乎自己了。"CC说。

"对。"Echo说，"因为我在乎自己了。

题目描述

$n$个哨兵排成环，第$i$个站岗疲劳$a_i$。相邻不能同时休息，求最小总疲劳。

输入格式

第一行$n$。第二行$n$个整数$a_i$。

输出格式

最小总疲劳。

输入样例

3 2
0
2
1

输出样例

2

提示

• 分类：第1个站岗或休息。
• $dp[i][0]=dp[i-1][1]$，$dp[i][1]=\min(dp[i-1][0],dp[i-1][1])+a_i$。
• 时间复杂度$O(n)$。