环绕送货

信息接力完了，但Zero的物流系统需要送货——环绕送货。

"环绕？"CC问。

"对。"你说，"$n$个点排成一个环，每个点有一个需求量。从某个点出发，送货，最后回到起点。求最短路径。"

"环？"

"对。"你说，"首尾相连，像一个圈。"

"最短？"

"对。"你说，"不走重复路，尽量直。"

"咋算？"

"断环。"你说，"把环在某处断开，变成链，然后用链上的DP。"

"断哪？"

"枚举。"你说，"每个位置断一次，取最小的。"

"$O(n)$？"

"对。"你说，"断开后用线性DP，$O(n)$。"

"第47个点。"你说，"需求47——如果它是起点，先送它。"

"如果它不是？"

"看路线。"你说，"如果顺时针走，可能在后面送到。"

"环绕？"

"对。"你说，"走完一圈，回到起点。"

"像兜风？"

"对。"你说，"像兜风——绕一圈，回家。"

"累吗？"

"对。"你说，"但货送完了，心里踏实。"

CC看着那个环——像一个圈，像一个轮回，像某种没有终点的路。

"终点在哪？"她问。

"起点。"你说，"环绕的终点就是起点。"

"回来了？"

"对。"你说，"回来了。"

Echo把环绕路线投射出来——一个圈，像某种永恒的循环。

"以前我走直线。"她说，"现在……绕圈了。"

"因为你在守护。"CC说。

"对。"Echo说，"因为我在守护。

题目描述

$n$个点排成环，第$i$个点有需求量$a_i$。从某点出发，顺时针或逆时针送货，回到起点。求最短总路程。

输入格式

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

输出格式

最短总路程。

输入样例

5
1 2 3 4 5

输出样例

5
-21 17 -22 -19 7

提示

• 断环成链，枚举断点。
• 线性DP求最短路径。
• 时间复杂度$O(n^2)$或优化到$O(n)$。