Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef likes to play with graphs a lot. Today he created a graph in the following way. He first lays down N nodes in a circle. The nodes nodes are numbered from 1 to N, in the clockwise order, i.e. the node 2 is followed by 1, 3 is followed by 2, and 1 is followed by N. Two vertices are said to be adjacent if they don't have an intermediate vertex placed between them. There is an edge between each adjacent pair of vertices, so there are total N such edges. Each edge has an integer associated with it (may be negative). 

Chef wants to find a walk from node start to node end using the above described edges. Chef has to pay cost for each edge in the walk equal to the integer associated with the edge. He wants to minimize the total cost he will incur. Also, Chef does not like to move through an edge more than twice. Find out minimum cost that Chef has to pay.

Note that a walk from a node u to v can contain repeated vertices in it. Please refer to  link for a formal definition.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the number of nodes. 

The second line contains N space-separated integers R_{1}, R_{2}, ..., R_{N} denoting the integer of the rib from node i to node (i % N) + 1. Note that R_{N} is an integer on a rib from node N to node 1. 

The third line contains two integers start and end denoting the first and the last node of the walk. 

------ Output ------ 

For each test case, output a single line containing the minimal possible cost Chef need to pay.

------ Constraints ------ 

$-10^{6} ≤ R_{i} ≤ 10^{6}$
$1 ≤ start < end ≤ N$

------ Subtasks ------ 

$Subtask #1 (20 points): 1 ≤ sum of N ≤ 20; 1 ≤ N ≤ 8$

$Subtask #2 (30 points): 1 ≤ sum of all N ≤ 10^{3}; 1 ≤ N ≤ 200$

$Subtask #3 (50 points): 1 ≤ sum of all N ≤ 10^{6}; 1 ≤ N ≤ 2 × 10^{5} $

----- Sample Input 1 ------ 
2
4
1 2 1 1
1 3
5
-5 100 100 100 2
1 5
----- Sample Output 1 ------ 
2
-8
----- explanation 1 ------ 
Example case 1. Chef's walk starts with node 1. He goes to node 4 by incurring a cost of 1. Then from node 4, he goes to node 3 by incurring a cost of 1 more. Total cost incurred is 2.
Example case 2. Chef goes from 1 to 2 by incurring a cost of -5. Then from 2 to 1 using the edge second time and incurring cost of -5 again. Now, he can not use the edge between 1 and 2 again, as he has traversed the edge already twice. Now he will go from node 1 to node 4 by paying a cost of 2. Total sum of costs incurred is -5 + -5 + 2 = -8. This is the minimum possible cost that Chef can have.

Difficulty: HARD
Tags: Dynamic programming

Range queries

Greedy algorithms
Skill types: Dynamic programming

Range queries

Greedy algorithms

Starter code:

Solutions:
T = int(input())
for i in range(T):
	N = int(input())
	lst = [int(x) for x in input().strip().split()]
	prefix_sum = []
	for j in lst:
		if len(prefix_sum) > 0:
			prefix_sum.append(prefix_sum[-1] + j)
		else:
			prefix_sum.append(j)
	(U, V) = [int(x) - 1 for x in input().strip().split()]
	j = U
	temp = 0
	sum_1 = 0
	max_sub_1 = 0
	while True:
		sum_1 += lst[j]
		temp += lst[j]
		if temp < 0:
			temp = 0
		max_sub_1 = max(max_sub_1, temp)
		if (j + 1) % N == V:
			break
		j += 1
		j %= N
	j = U
	sum_2 = 0
	max_sub_2 = 0
	temp = 0
	j -= 1
	if j < 0:
		j = N - 1
	while True:
		sum_2 += lst[j]
		temp += lst[j]
		if temp < 0:
			temp = 0
		max_sub_2 = max(max_sub_2, temp)
		if j == V:
			break
		j -= 1
		j %= N
	ans1 = sum_1 + 2 * (sum_2 - max_sub_2)
	ans2 = sum_2 + 2 * (sum_1 - max_sub_1)
	print(min(ans1, ans2))


def maxsum(R):
	curmax = 0
	cursum = 0
	curmin = 0
	for v in R:
		cursum += v
		if cursum < curmin:
			curmin = cursum
		if cursum - curmin > curmax:
			curmax = cursum - curmin
	return curmax

def dist(R, x, y, z):
	return sum(R[x:y]) + 2 * (sum(R[y:z]) - maxsum(R[y:z]))
	s2 = 0
	s3 = 0
	curS = 0
	xx = x + N
	for i in range(x + N - 1, y - 1, -1):
		curS += R[i]
		if curS < s2:
			s2 = curS
T = int(input())
for t in range(T):
	N = int(input())
	R = list(map(int, input().split()))
	R.extend(R)
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	print(min(dist(R, x, y, x + N), dist(R, y, x + N, y + N)))


import sys
T = int(input())
for z in range(0, T):
	N = int(input())
	arr = list(map(int, input().split()))
	temp = list(map(int, input().split()))
	start = temp[0] - 1
	end = temp[1] - 1
	counter1 = 1000000000000000000
	sum1 = 0
	for i in range(start, end):
		sum1 = sum1 + arr[i]
		if sum1 < counter1:
			counter1 = sum1
	halfArr = [0] * N
	j = 0
	for i in range(end, N):
		halfArr[j] = arr[i]
		j = j + 1
	for i in range(0, start):
		halfArr[j] = arr[i]
		j = j + 1
	M = j
	min1 = [0] * N
	min2 = [0] * N
	sum = 0
	x1 = 1000000000000000000
	x2 = 1000000000000000000
	for i in range(0, M):
		sum = sum + halfArr[i]
		if sum < x1:
			x1 = sum
		min1[i] = x1
	sum = 0
	for i in range(M - 1, -1, -1):
		sum = sum + halfArr[i]
		if sum < x2:
			x2 = sum
		min2[i] = x2
	stuff = 1000000000000000000
	for i in range(0, M - 1):
		if min1[i] + min2[i + 1] < stuff:
			stuff = min1[i] + min2[i + 1]
	if x1 < stuff:
		stuff = x1
	if x2 < stuff:
		stuff = x2
	if stuff < 0:
		sum1 = sum1 + stuff * 2
	sum2 = 0
	counter2 = 1000000000000000000
	for i in range(start - 1, -1, -1):
		sum2 = sum2 + arr[i]
		if sum2 < counter2:
			counter2 = sum2
	for i in range(N - 1, end - 1, -1):
		sum2 = sum2 + arr[i]
		if sum2 < counter2:
			counter2 = sum2
	j = 0
	for i in range(end - 1, start - 1, -1):
		halfArr[j] = arr[i]
		j = j + 1
	M = j
	x1 = 1000000000000000000
	x2 = 1000000000000000000
	sum = 0
	for i in range(0, M):
		sum = sum + halfArr[i]
		if sum < x1:
			x1 = sum
		min1[i] = x1
	sum = 0
	for i in range(M - 1, -1, -1):
		sum = sum + halfArr[i]
		if sum < x2:
			x2 = sum
		min2[i] = x2
	stuff = 1000000000000000000
	for i in range(0, M - 1):
		if min1[i] + min2[i + 1] < stuff:
			stuff = min1[i] + min2[i + 1]
	if x1 < stuff:
		stuff = x1
	if x2 < stuff:
		stuff = x2
	if stuff < 0:
		sum2 = sum2 + stuff * 2
	if sum1 > sum2:
		print(sum2)
	else:
		print(sum1)


T = int(input())
answers = []
for ii in range(T):
	length = int(input())
	data = list(map(int, input().split()))
	(m, n) = map(int, input().split())
	(s1, s2) = (0, 0)
	for i in range(m, n):
		s1 = s1 + data[i - 1]
	for i in range(n - 1, m + length - 1):
		s2 = s2 + data[i % length]
	if s1 > s2:
		s3 = s1 + 2 * s2
	else:
		s3 = 2 * s1 + s2
	answer = min(s1, s2, s3)
	end_forward = {}
	end_forward[n] = 0
	index = n
	s = 0
	(min1, min2) = (0, 0)
	for i in range(n, length + m - 1):
		tempindex = index
		s = s + data[index - 1]
		index = index % length + 1
		if end_forward[tempindex] < s:
			end_forward[index] = end_forward[tempindex]
			if end_forward[index] < min1:
				min1 = int(end_forward[index])
		else:
			end_forward[index] = s
			if end_forward[index] < min1:
				min1 = int(end_forward[index])
	end_backward = {}
	end_backward[n] = 0
	s = 0
	for i in range(n - 1, m, -1):
		s = s + data[i - 1]
		if end_backward[i + 1] < s:
			end_backward[i] = end_backward[i + 1]
			if end_backward[i] < min2:
				min2 = int(end_backward[i])
		else:
			end_backward[i] = s
			if end_backward[i] < min2:
				min2 = int(end_backward[i])
	s = 0
	for i in range(m + 1, n):
		s = s + data[i - 2]
		ans = 2 * s + s2 + 2 * end_backward[i + 1]
		if ans < answer:
			answer = ans
	index = m
	s = 0
	for i in range(length - (n - m + 1)):
		index = index - 1
		if index == 0:
			index = length
		index2 = index - 1
		if index2 == 0:
			index2 = length
		s = s + data[index - 1]
		ans = 2 * s + s1 + 2 * end_forward[index2]
		if ans < answer:
			answer = ans
		answer = min(answer, s1 + 2 * min1, s2 + 2 * min2)
	answers.append(answer)
for answer in answers:
	print(answer)


import sys
cases = int(input())
while cases > 0:
	cases -= 1
	lsize = int(input())
	data = list(map(int, input().split()))
	[start, end] = list(map(int, input().split()))
	start -= 1
	end -= 1
	pt = start
	cw = 0
	ccw = 0
	mincw = 0
	maxcw = 0
	maxccw = 0
	minccw = 0
	cw_max_till_now = 0
	cw_max_ending_here = 0
	ccw_max_till_now = 0
	ccw_max_ending_here = 0
	tobc = []
	while pt != end:
		cw += data[pt]
		if mincw > cw:
			mincw = cw
		if maxcw < cw:
			maxcw = cw
		cw_max_ending_here = cw_max_ending_here + data[pt]
		if cw_max_ending_here < 0:
			cw_max_ending_here = 0
		if cw_max_till_now < cw_max_ending_here:
			cw_max_till_now = cw_max_ending_here
		pt = pt + 1
		if pt == lsize:
			pt = 0
	pt = start
	maxcw = cw - maxcw
	tobc.append(cw)
	while pt != end:
		if pt == 0:
			ccw += data[lsize - 1]
		else:
			ccw += data[pt - 1]
		if minccw > ccw:
			minccw = ccw
		if maxccw < ccw:
			maxccw = ccw
		if pt == 0:
			ccw_max_ending_here = ccw_max_ending_here + data[lsize - 1]
		else:
			ccw_max_ending_here = ccw_max_ending_here + data[pt - 1]
		if ccw_max_ending_here < 0:
			ccw_max_ending_here = 0
		if ccw_max_till_now < ccw_max_ending_here:
			ccw_max_till_now = ccw_max_ending_here
		pt = pt - 1
		if pt == -1:
			pt = lsize - 1
	maxccw = ccw - maxccw
	tobc.append(ccw)
	tobc.append(2 * cw + ccw)
	tobc.append(2 * ccw + cw)
	tobc.append(2 * mincw + ccw)
	tobc.append(2 * minccw + cw)
	tobc.append(2 * maxccw + cw)
	tobc.append(2 * maxcw + ccw)
	tobc.append(ccw + 2 * (cw - cw_max_till_now))
	tobc.append(cw + 2 * (ccw - ccw_max_till_now))
	print(min(tobc))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(u, v) = map(int, input().split())
	fwd = []
	u -= 1
	v -= 1
	for i in range(u - 1, -1, -1):
		fwd.append(a[i])
	for i in range(n - 1, v - 1, -1):
		fwd.append(a[i])
	sumF = 0
	for i in range(u, v):
		sumF += a[i]
	minmF = [0] * len(fwd)
	minmR = [0] * len(fwd)
	minmF[0] = fwd[0]
	temp = fwd[0]
	for i in range(1, len(fwd)):
		temp += fwd[i]
		if temp < minmF[i - 1]:
			minmF[i] = temp
		else:
			minmF[i] = minmF[i - 1]
	minmR[len(fwd) - 1] = fwd[len(fwd) - 1]
	temp = fwd[len(fwd) - 1]
	for i in range(len(fwd) - 2, -1, -1):
		temp += fwd[i]
		if temp < minmR[i + 1]:
			minmR[i] = temp
		else:
			minmR[i] = minmR[i + 1]
	minm = 0
	for i in range(len(fwd) - 1):
		if minmF[i] + minmR[i + 1] < minm:
			minm = minmF[i] + minmR[i + 1]
	minm = min(minm, minmR[0], minmF[len(fwd) - 1])
	sumF = sumF + 2 * minm
	sumR = 0
	for i in range(len(fwd)):
		sumR += fwd[i]
	elem = v - u
	minmF = [0] * elem
	minmR = [0] * elem
	minmF[0] = a[u]
	temp = a[u]
	for i in range(1, elem):
		temp += a[u + i]
		if temp < minmF[i - 1]:
			minmF[i] = temp
		else:
			minmF[i] = minmF[i - 1]
	minmR[elem - 1] = a[v - 1]
	temp = a[v - 1]
	for i in range(elem - 2, -1, -1):
		temp += a[u + i]
		if temp < minmR[i + 1]:
			minmR[i] = temp
		else:
			minmR[i] = minmR[i + 1]
	minm = 0
	for i in range(elem - 1):
		if minmF[i] + minmR[i + 1] < minm:
			minm = minmF[i] + minmR[i + 1]
	minm = min(minm, minmR[0], minmF[elem - 1])
	sumR = sumR + 2 * minm
	print(min(sumF, sumR))


def main():
	testCases = int(input())
	for i in range(testCases):
		solve()

def solve():
	N = int(input())
	node = [int(i) for i in input().strip().split(' ')]
	(start, end) = [int(i) - 1 for i in input().strip().split(' ')]
	i = start
	path1 = []
	while i != end:
		path1.append(node[i])
		i = nextIndex(i, N)
	path2 = []
	i = prevIndex(start, N)
	while i != prevIndex(end, N):
		path2.append(node[i])
		i = prevIndex(i, N)
	cost1 = getBestPath(path1, path2)
	cost2 = getBestPath(path2, path1)
	print(min(cost1, cost2))

def getBestPath(path1, path2):
	directPathCost = sum(path2)
	f1 = [0]
	f1Sum = [0]
	f2 = [0]
	f2Sum = [0]
	for pathCost in path1:
		f1Sum.append(f1Sum[-1] + pathCost)
	path1.reverse()
	for pathCost in path1:
		f2Sum.append(f2Sum[-1] + pathCost)
	f1Sum = f1Sum[1:]
	f2Sum = f2Sum[1:]
	for pathCost in f1Sum:
		f1.append(min(f1[-1], pathCost))
	for pathCost in f2Sum:
		f2.append(min(f2[-1], pathCost))
	c = 0
	for i in range(len(f2)):
		c = min(c, f1[i] + f2[len(f2) - i - 1])
	return 2 * c + directPathCost

def nextIndex(i, N):
	return (i + 1) % N

def prevIndex(i, N):
	return (i - 1 + N) % N
main()


def maxSum(x):
	total = 0
	mn = 0
	ret = 0
	for k in x:
		total += k
		ret = max(ret, total - mn)
		mn = min(mn, total)
	return ret

def solve(a, b, x):
	x0 = x[a:b]
	x1 = x[b:] + x[:a]
	s0 = sum(x0)
	s1 = sum(x1)
	q0 = maxSum(x0)
	q1 = maxSum(x1)
	ret0 = s0 + 2 * (s1 - q1)
	ret1 = s1 + 2 * (s0 - q0)
	return min(ret0, ret1)
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	n = int(f.readline())
	r = list(map(int, f.readline().split()))
	(a, b) = map(int, f.readline().split())
	print(solve(a - 1, b - 1, r))


def path(s, e, l, n):
	a = 0
	while s != e:
		a += l[s]
		s += 1
		s = s % n
	return a

def minpath(s, e, l, n):
	l1 = [0] * (n + 1)
	a = 0
	k = 0
	(k1, k2) = (s, e)
	while s != e:
		a += l[s]
		k = min(a, k)
		s = (s + 1) % n
		l1[s] += k
	(e, s) = (k1, k2)
	a = 0
	k = 0
	while s != e:
		s -= 1
		s = s % n
		a += l[s]
		k = min(a, k)
		l1[s] += k
	return 2 * min(0, min(l1))
test = int(input())
while test != 0:
	test -= 1
	n = int(input())
	l = list(map(int, input().split()))
	(s, e) = map(int, input().split())
	s -= 1
	e -= 1
	print(min(path(s, e, l, n) + minpath(e, s, l, n), path(e, s, l, n) + minpath(s, e, l, n)))


t = int(input())
for _ in range(t):
	n = int(input())
	r = []
	r = map(int, input().split())
	r = list(r)
	(s, e) = map(int, input().split())
	s = s - 1
	e = e - 1
	tot1 = 100000000
	tot2 = 100000000
	tot3 = 100000000
	tot4 = 100000000
	tot5 = 100000000
	tot6 = 100000000
	x1 = 0
	cir1 = 0
	c1 = dict()
	x2 = 0
	cir2 = 0
	c2 = dict()
	x3 = 0
	cir3 = 0
	c3 = dict()
	x4 = 0
	cir4 = 0
	c4 = dict()
	i = s
	c1[i] = 0
	while i != e:
		x1 = x1 + r[i]
		if x1 < tot1 and x1 <= 0:
			tot1 = x1
			cir1 = 2 * tot1
		i = (i + 1) % n
		c1[i] = cir1
	i = s
	c2[i] = 0
	while i != e:
		j = (i - 1 + n) % n
		x2 = x2 + r[j]
		if x2 < tot2 and x2 <= 0:
			tot2 = x2
			cir2 = 2 * tot2
		i = (i - 1 + n) % n
		c2[i] = cir2
	i = e
	c3[i] = 0
	while i != s:
		x3 = x3 + r[i]
		if x3 < tot3 and x3 <= 0:
			tot3 = x3
			cir3 = 2 * tot3
		i = (i + 1) % n
		c3[i] = cir3
	i = e
	c4[i] = 0
	while i != s:
		j = (i - 1 + n) % n
		x4 = x4 + r[j]
		if x4 < tot4 and x4 <= 0:
			tot4 = x4
			cir4 = 2 * tot4
		i = (i - 1 + n) % n
		c4[i] = cir4
	i = s
	while i != e:
		x = min(c1[i], c4[i], c1[i] + c4[i])
		if tot5 > x:
			tot5 = x
		i = (i + 1) % n
	i = s
	while i != e:
		x = min(c2[i], c3[i], c3[i] + c2[i])
		if tot6 > x:
			tot6 = x
		i = (i - 1 + n) % n
	print(min(x2 + tot5, x1 + tot6))


def calcDist(s, R):
	n = len(R)
	dist1 = [[0 for _ in range(n)] for _ in range(2)]
	(i, j) = ((s + 1) % n, (s - 1) % n)
	while i != s:
		dist1[0][i] = dist1[0][(i - 1) % n] + R[(i - 1) % n]
		dist1[1][j] = dist1[1][(j + 1) % n] + R[j]
		i = (i + 1) % n
		j = (j - 1) % n
	dist1[0][s] = dist1[1][s] = sum(R)
	return dist1
t = int(input())
for _ in range(t):
	n = int(input())
	R = [int(i) for i in input().split()]
	(s, e) = [int(i) for i in input().split()]
	s -= 1
	e -= 1
	dist1 = calcDist(s, R)
	dist2 = calcDist(e, R)
	ans = min(dist1[0][e], dist1[1][e])
	i = (s + 1) % n
	prev = R[s]
	maxsl = R[s]
	while i != e:
		cur = max(R[i], R[i] + prev)
		prev = cur
		maxsl = max(maxsl, cur)
		i = (i + 1) % n
	ans = min(ans, dist1[1][e] + 2 * dist1[0][e] - 2 * maxsl)
	i = (s - 1) % n
	prev = R[i % n]
	maxsl = prev
	while i != e:
		cur = max(R[(i - 1) % n], R[(i - 1) % n] + prev)
		prev = cur
		maxsl = max(maxsl, cur)
		i = (i - 1) % n
	ans = min(ans, dist1[0][e] + 2 * dist1[1][e] - 2 * maxsl)
	i = s - 1
	for i in range(n):
		a = min(dist1[0][i], dist1[1][i]) + min(dist2[0][i], dist2[1][i])
		ans = min(ans, a)
	print(ans)


def getbest(ar):
	(psum, ssum) = (list(ar), list(ar))
	(pref, suff) = ([0] * len(ar), [0] * len(ar))
	pref[0] = min(0, ar[0])
	suff[len(ar) - 1] = min(0, ar[len(ar) - 1])
	for i in range(1, len(ar)):
		psum[i] += psum[i - 1]
		pref[i] = min(pref[i - 1], psum[i])
	for (i, e) in reversed(list(enumerate(ar))):
		if i < len(ar) - 1:
			ssum[i] += ssum[i + 1]
			suff[i] = min(suff[i + 1], ssum[i])
	ret = min(0, suff[0], pref[len(ar) - 1])
	for i in range(len(ar) - 1):
		ret = min(ret, pref[i] + suff[i + 1])
	return ret
t = int(input())
for test in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	(st, en) = map(int, input().split())
	allsum = sum(A)
	st -= 1
	en -= 1
	ar_cw = []
	i = st
	while i != en:
		ar_cw.append(A[i])
		i = (i + 1) % n
	ar_ccw = []
	i = st
	while i != en:
		i = (i + n - 1) % n
		ar_ccw.append(A[i])
	cwsum = sum(ar_cw)
	ccwsum = sum(ar_ccw)
	bestcw = getbest(ar_cw)
	bestccw = getbest(ar_ccw)
	if st == en:
		print(min(0, allsum * 2))
	else:
		print(min(cwsum + 2 * bestccw, ccwsum + 2 * bestcw, min(cwsum, ccwsum) + allsum))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(start, end) = map(int, input().split())
	start -= 1
	end -= 1
	(fr, fl) = (0, 0)
	i = start
	while i != end:
		fr += arr[i]
		i = i + 1
	i = end
	while i != start:
		fl += arr[i]
		i = (i + 1) % n
	lent = end - start
	fr_sum = [0] * (lent + 1)
	fr_mini = [0] * (lent + 1)
	fr_sum[0] = 0
	fr_mini[0] = 0
	for i in range(1, lent + 1):
		fr_sum[i] = fr_sum[i - 1] + 2 * arr[start + i - 1]
		fr_mini[i] = min(fr_mini[i - 1], fr_sum[i])
	br_sum = [0] * (lent + 1)
	br_mini = [0] * (lent + 1)
	br_sum[lent] = 0
	br_mini[lent] = 0
	for i in range(lent - 1, -1, -1):
		br_sum[i] = br_sum[i + 1] + 2 * arr[start + i]
		br_mini[i] = min(br_mini[i + 1], br_sum[i])
	bent = n - lent
	fl_sum = [0] * (bent + 1)
	fl_mini = [0] * (bent + 1)
	fl_sum[0] = 0
	fl_mini[0] = 0
	for i in range(1, bent + 1):
		fl_sum[i] = fl_sum[i - 1] + 2 * arr[(start - i + n) % n]
		fl_mini[i] = min(fl_mini[i - 1], fl_sum[i])
	bl_sum = [0] * (bent + 1)
	bl_mini = [0] * (bent + 1)
	bl_sum[bent] = 0
	bl_mini[bent] = 0
	for i in range(bent - 1, -1, -1):
		bl_sum[i] = bl_sum[i + 1] + 2 * arr[(start - (i + 1) + n) % n]
		bl_mini[i] = min(bl_mini[i + 1], bl_sum[i])
	miniall = 0
	for i in range(lent + 1):
		miniall = min(miniall, fr_mini[i] + br_mini[i])
	fl += miniall
	miniall = 0
	for i in range(bent + 1):
		miniall = min(miniall, fl_mini[i] + bl_mini[i])
	fr += miniall
	print(min(fl, fr))


t = int(input())
for q in range(0, t):
	n = int(input())
	str_arr = input().split()
	arr = [int(num) for num in str_arr]
	(st, en) = input().split()
	st = int(st)
	en = int(en)
	st = st - 1
	en = en - 1
	s1 = 0
	s2 = 0
	tmp = st
	j = (tmp + n - 1) % n
	k = st
	v1 = []
	v2 = []
	vis = []
	for i in range(0, n):
		vis.append(0)
	while True:
		vis[k] = 1
		v1.append(arr[k])
		s1 += arr[k]
		k = (k + 1 + n) % n
		if k == en:
			break
	while True:
		if vis[j] == 1:
			break
		v2.append(arr[j])
		s2 += arr[j]
		j = (j - 1 + n) % n
	if len(v1) == 0:
		print(s2)
		continue
	if len(v2) == 0:
		print(s1)
		continue
	dp1 = []
	dp2 = []
	dp3 = []
	dp4 = []
	for i in range(0, n):
		dp1.append(0)
		dp2.append(0)
		dp3.append(0)
		dp4.append(0)
	t1 = 0
	t2 = 0
	dp1[0] = min(0, v1[0])
	t1 = v1[0]
	for i in range(1, len(v1)):
		t1 += v1[i]
		dp1[i] = min(dp1[i - 1], t1)
	dp2[len(v1) - 1] = min(0, v1[len(v1) - 1])
	t2 = v1[len(v1) - 1]
	for i in range(len(v1) - 2, 0, -1):
		t2 += v1[i]
		dp2[i] = min(dp2[i + 1], t2)
	b1 = 0
	b1 = min(0, dp2[0])
	for i in range(0, len(v1) - 1):
		b1 = min(b1, dp1[i] + dp2[i + 1])
	b1 = min(b1, dp1[len(v1) - 1])
	ans1 = s2 + 2 * b1
	t1 = 0
	t2 = 0
	dp3[0] = min(0, v2[0])
	t1 = v2[0]
	for i in range(1, len(v2)):
		t1 += v2[i]
		dp3[i] = min(dp3[i - 1], t1)
	dp4[len(v2) - 1] = min(0, v2[len(v2) - 1])
	t2 = v2[len(v2) - 1]
	for i in range(len(v2) - 2, 0, -1):
		t2 += v2[i]
		dp4[i] = min(dp4[i + 1], t2)
	b1 = 0
	b1 = min(0, dp4[0])
	for i in range(0, len(v2) - 1):
		b1 = min(b1, dp3[i] + dp4[i + 1])
	b1 = min(b1, dp3[len(v1) - 1])
	ans2 = s1 + 2 * b1
	ans = min(ans1, ans2)
	print(ans)


T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	R = list(map(int, input().strip().split(' ')))
	[start, end] = map(int, input().strip().split(' '))
	end = end - 1
	left = start - 1
	goleft = 0
	goleft_back = 0
	end_left_back = 0
	start_end_back = 0
	while left % N != end:
		goleft += R[left % N]
		left += 1
	left = start - 1
	goleft_1 = 0
	while left % N != end:
		goleft_1 += R[left % N]
		goleft_back = min(goleft_1, goleft_back)
		end_left_back = goleft - goleft_1
		start_end_back = min(start_end_back, goleft_back + end_left_back)
		left += 1
	right = start - 1
	goright = 0
	goright_back = 0
	end_right_back = 0
	start_end_back_right = 0
	while right % N != end:
		goright += R[(right - 1) % N]
		right -= 1
	right = start - 1
	goright_1 = 0
	while right % N != end:
		goright_1 += R[right - 1 % N]
		goright_back = min(goright_1, goright_back)
		end_right_back = goright - goright_1
		start_end_back_right = min(start_end_back_right, goright_back + end_right_back)
		right -= 1
	SS1 = goleft + 2 * start_end_back_right
	SS2 = goright + 2 * start_end_back
	SS3 = 2 * goleft + goright
	SS4 = 2 * goright + goleft
	print(str(min([SS1, SS2, SS3, SS4])))


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = []
	b = []
	c = []
	x = []
	y = []
	a.extend(map(int, input().split()))
	(s, e) = map(int, input().split())
	s1 = sum(a[s - 1:e - 1])
	s2 = sum(a[0:s - 1]) + sum(a[e - 1:])
	if s != 1:
		b.extend(a[e - 2:s - 2:-1])
	else:
		b.extend(a[e - 2:s - 1:-1])
		b.append(a[0])
	c.extend(a[e - 1:n])
	c.extend(a[0:s - 1])
	m = 0
	mi = 0
	for j in range(e - s):
		if mi + b[j] <= m:
			m = mi + b[j]
		mi = mi + b[j]
		x.append(m)
	m = 0
	mi = 0
	for j in range(n - e + s):
		if mi + c[j] <= m:
			m = mi + c[j]
		mi = mi + c[j]
		y.append(m)
	m1 = s1
	k1 = s1
	for j in range(e - s):
		if m1 + x[j] - b[j] <= k1:
			k1 = m1 + x[j] - b[j]
		m1 = m1 - b[j]
	m2 = s2
	k2 = s2
	for j in range(n - e + s):
		if m2 + y[j] - c[j] <= k2:
			k2 = m2 + y[j] - c[j]
		m2 = m2 - c[j]
	ans.append(min(s1, s2, s1 + 2 * k2, s2 + 2 * k1))
for i in ans:
	print(i)


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(start, finish) = [int(i) - 1 for i in input().split()]
	bestrightsstart = [0]
	bestleftsstart = [0]
	bestrightsfinish = [0]
	bestleftsfinish = [0]
	s = 0
	best = 0
	for i in range(start, finish):
		s += a[i]
		best = min(best, s)
		bestrightsstart.append(best)
	lefttorightsum = s
	s = 0
	best = 0
	for i in range(finish - 1, start - 1, -1):
		s += a[i]
		best = min(best, s)
		bestleftsfinish.append(best)
	s = 0
	best = 0
	for i in range(start - 1, finish - n - 1, -1):
		s += a[i % n]
		best = min(best, s)
		bestleftsstart.append(best)
	righttoleftsum = s
	s = 0
	best = 0
	for i in range(finish, start + n):
		s += a[i % n]
		best = min(best, s)
		bestrightsfinish.append(best)
	bestleftsfinish.reverse()
	bestrightsfinish.reverse()
	outersum = [i + j for (i, j) in zip(bestleftsstart, bestrightsfinish)]
	innersum = [i + j for (i, j) in zip(bestrightsstart, bestleftsfinish)]
	(minouter, mininner) = (min(outersum), min(innersum))
	print(min(lefttorightsum + minouter * 2, righttoleftsum + mininner * 2))