解题思路

• 将公路视为一个有 n 个站点的环，给出顺时针相邻两站的距离数组 a[1..n]（其中 a[n] 为第 n 站到第 1 站的距离）。

• 要求从站点 x 到 y 的最短路程。显然只有两种走法：

  1. 顺时针从较小编号走到较大编号的区间和；
  2. 逆时针，其距离为“环总长 − 上述区间和”。

• 因此先计算区间和 segment = sum(a[min(x,y)] .. a[max(x,y)-1]) 与总和 total = sum(a[1..n])，答案为 min(segment, total - segment)。

• 相关算法：前缀和/区间求和（此处直接一次线性求和即可）。

题目内容

有一个环形的公路，上面共有 $n$ 站，现在给定了顺时针第站到第 $i+1$ 站之间的距离(特殊的，也给出了第 $n$ 站到第 $1$ 站的距离)。小美想沿着公路第 $x$ 站走到第 $y$ 站，她想知道最短的距离是多少?

输入描述

第一行输入一个正整数 $n$ ，代表站的数量.

第二行输入 $n$ 个正整数,前 $n-1$ 个数代表顺时针沿着公路走， $i$ 站到第 $i+1$ 站之间的距离;最后一个正整数代表顺时针沿着公路走，第 $n$ 站到第 $1$ 站的距离。

第三行输入两个正整数 $x$ 和 $y$ ,代表小美的出发地和目的地。

$1≤n≤10^5$

$1≤a_i≤10^9$

$1≤x,y≤n$

输出描述

一个正整数，代表小美走的最短距离。

样例1

输入

3
1 2 2
2 3

输出

2

样例2

输入

3
1 2 2
1 3

输出

2