Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef has a machine which he uses to rotate sequences. If he puts a sequence $S_{1}, S_{2}, \ldots, S_{N}$ into the machine, it produces the sequence $S_{2}, S_{3}, \ldots, S_{N}, S_{1}$, i.e. the first element of the sequence is moved to the end.

Chef is definitely not a newbie ― he knows about trivial things like finding the maximum sum of a contiguous subsequence. Therefore, he now made a difficult problem to challenge himself:

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. For each $k$ ($0 ≤ k ≤ N-1$), consider the sequence produced by inserting it into the machine repeatedly $k$ times (i.e. inserting $A$ into the machine and replacing $A$ by the sequence it produces, $k$ times); find the maximum sum of a non empty contiguous subsequence of this sequence.

However, to solve this problem, Chef needs the help of a pro. Solve it for him. 

------  Input ------
The first line of the input contains a single 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$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should denote the largest sum of a non empty contiguous subsequence of the sequence produced by the machine after $i-1$ repeated insertions.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$|A_{i}| ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------ 
1

4

-5 4 1 2
----- Sample Output 1 ------ 
7 7 4 5
----- explanation 1 ------ 
Example case 1:
- After zero insertions, $A = [-5, 4, 1, 2]$. The contiguous subsequence with the maximum sum is $A = [4, 1, 2]$.
- After one insertion, $A = [4, 1, 2, -5]$. The contiguous subsequence with the maximum sum is $A = [4, 1, 2]$.
- After two insertions, $A = [1, 2, -5, 4]$. The contiguous subsequence with the maximum sum is $A = [4]$.
- After three insertions, $A = [2, -5, 4, 1]$. The contiguous subsequence with the maximum sum is $A = [4, 1]$.

Difficulty: VERY_HARD
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a1 = [0] * (n + 1)
	b1 = [0] * (n + 1)
	a1[0] = b1[0] = -math.inf
	m1 = 0
	s1 = 0
	for i in range(n):
		s1 += arr[i]
		a1[i + 1] = max(a1[i], s1 - m1)
		b1[i + 1] = max(b1[i], s1)
		m1 = min(m1, s1)
	arr.reverse()
	a2 = [0] * (n + 1)
	b2 = [0] * (n + 1)
	a2[0] = b2[0] = -math.inf
	m2 = 0
	s2 = 0
	for i in range(n):
		s2 += arr[i]
		a2[i + 1] = max(a2[i], s2 - m2)
		b2[i + 1] = max(b2[i], s2)
		m2 = min(m2, s2)
	for i in range(n):
		ans = max(a1[i], a2[n - i], b1[i] + b2[n - i])
		print(ans, end=' ')


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	before = [a[0]]
	ending = [a[0]]
	maxi = 0
	curr = 0
	for i in range(1, len(a)):
		ending.append(max(a[i], ending[i - 1] + a[i]))
	maxi = a[0]
	for i in range(1, len(a)):
		before.append(max(ending[i], maxi))
		if before[i] > maxi:
			maxi = before[i]
	ending1 = [a[0]]
	b = a[:]
	b.reverse()
	after = [b[0]]
	starting = [b[0]]
	maxi = 0
	curr = 0
	for i in range(1, len(b)):
		starting.append(max(b[i], starting[i - 1] + b[i]))
	maxi = b[0]
	for i in range(1, len(b)):
		after.append(max(starting[i], maxi))
		if after[i] > maxi:
			maxi = after[i]
	pre = [a[0]]
	ma = a[0]
	for i in range(1, len(a)):
		ma += a[i]
		pre.append(max(ma, pre[i - 1]))
	suff = [b[0]]
	ma = b[0]
	for i in range(1, len(a)):
		ma += b[i]
		suff.append(max(suff[i - 1], ma))
	starting.reverse()
	after.reverse()
	ans = [after[0]]
	suff.reverse()
	for i in range(1, len(a)):
		ans.append(max(after[i], max(before[i - 1], pre[i - 1] + suff[i])))
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.insert(0, 0)
	max_pre = [0 for i in range(n + 2)]
	max_suf = [0 for i in range(n + 2)]
	pre = [0 for i in range(n + 2)]
	suf = [0 for i in range(n + 2)]
	(max_pre[0], max_suf[n + 1], pre[0], suf[n + 1]) = (-float('inf'), -float('inf'), -float('inf'), -float('inf'))
	total = 0
	max_till_here = -float('inf')
	for i in range(1, n + 1):
		total += lst[i]
		max_till_here = max(max_till_here + lst[i], lst[i])
		max_pre[i] = max(max_pre[i - 1], max_till_here)
		pre[i] = max(pre[i - 1], total)
	total = 0
	max_till_here = -float('inf')
	for i in range(n, 0, -1):
		total += lst[i]
		max_till_here = max(max_till_here + lst[i], lst[i])
		max_suf[i] = max(max_suf[i + 1], max_till_here)
		suf[i] = max(suf[i + 1], total)
	for i in range(0, n):
		f = max_suf[i + 1]
		s = max_pre[i]
		t = pre[i] + suf[i + 1]
		print(max(f, s, t), end=' ')
	print()


ts = int(input())
while ts > 0:
	n = int(input())
	a = list(map(int, input().split()))
	pre = [0] * n
	for i in range(n):
		if i == 0:
			pre[i] = a[i]
		else:
			pre[i] = max(pre[i - 1] + a[i], a[i])
	suf = [0] * n
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suf[i] = a[i]
		else:
			suf[i] = max(suf[i + 1] + a[i], a[i])
	mpre = [0] * n
	msuf = [0] * n
	mpre[0] = pre[0]
	for i in range(1, n):
		mpre[i] = max(mpre[i - 1], pre[i])
	msuf[n - 1] = suf[n - 1]
	for i in range(n - 2, -1, -1):
		msuf[i] = max(msuf[i + 1], suf[i])
	sum = 0
	for i in range(n):
		sum += a[i]
		if i == 0:
			pre[i] = sum
		else:
			pre[i] = max(pre[i - 1], sum)
	sum = 0
	for i in range(n - 1, -1, -1):
		sum += a[i]
		if i == n - 1:
			suf[i] = sum
		else:
			suf[i] = max(suf[i + 1], sum)
	for i in range(n):
		ans = -1 * 10 ** 10
		ans = max(ans, msuf[i])
		if i - 1 >= 0:
			ans = max(ans, mpre[i - 1])
			ans = max(ans, suf[i] + pre[i - 1])
		print(ans, end=' ')
	ts -= 1


import sys

def jaya(b, c, n, a):
	m = 0
	s = 0
	for i in range(n):
		s += a[i]
		b.append(max(b[i], s - m))
		c.append(max(c[i], s))
		m = min(m, s)
	return (b, c)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	Maxsub = [-sys.maxsize - 1]
	MaxsuRev = [-sys.maxsize - 1]
	Maxsumpre = [-sys.maxsize - 1]
	MaxsumpreRev = [-sys.maxsize - 1]
	B = A.copy()
	B = B[::-1]
	(Maxsub, Maxsumpre) = jaya(Maxsub, Maxsumpre, N, A)
	(MaxsuRev, MaxsumpreRev) = jaya(MaxsuRev, MaxsumpreRev, N, B)
	for i in range(N):
		ans = max(MaxsuRev[N - i], Maxsub[i])
		ans = max(ans, MaxsumpreRev[N - i] + Maxsumpre[i])
		print(ans, end=' ')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	b1 = [0] * (n + 1)
	b2 = [0] * (n + 1)
	c1 = [0] * (n + 1)
	c2 = [0] * (n + 1)
	arr1 = arr[::-1]
	b1[0] = -float('inf')
	b2[0] = -float('inf')
	c1[0] = -float('inf')
	c2[0] = -float('inf')
	s = 0
	msp = 0
	for i in range(n):
		s += arr[i]
		b1[i + 1] = max(b1[i], s - msp)
		c1[i + 1] = max(c1[i], s)
		msp = min(msp, s)
	s = 0
	msp = 0
	for i in range(n):
		s += arr1[i]
		b2[i + 1] = max(b2[i], s - msp)
		c2[i + 1] = max(c2[i], s)
		msp = min(msp, s)
	for i in range(n):
		print(max(b1[i], b2[n - i], c1[i] + c2[n - i]), end=' ')
	print()


def solve(arr, b, c, n):
	b[0] = c[0] = -float('inf')
	mps = 0
	s = 0
	for i in range(n):
		s += arr[i]
		b[i + 1] = max(b[i], s - mps)
		c[i + 1] = max(c[i], s)
		mps = min(mps, s)
	return (b, c)
for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(b1, c1) = solve(arr, [0] * (n + 1), [0] * (n + 1), n)
	arr.reverse()
	(b2, c2) = solve(arr, [0] * (n + 1), [0] * (n + 1), n)
	for i in range(n):
		ans = max(b1[i], b2[n - i], c1[i] + c2[n - i])
		print(ans, end=' ')


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	max1 = [None] * N
	max2 = [None] * N
	suffix = [None] * N
	prefix = [None] * N
	curr_max = A[N - 1]
	final_max = A[N - 1]
	max1[N - 1] = A[N - 1]
	for i in range(N - 2, -1, -1):
		curr_max = max(A[i], curr_max + A[i])
		final_max = max(final_max, curr_max)
		max1[i] = final_max
	curr_max = A[0]
	final_max = A[0]
	max2[1] = A[0]
	for i in range(1, N - 1):
		curr_max = max(A[i], curr_max + A[i])
		final_max = max(final_max, curr_max)
		max2[i + 1] = final_max
	curr_max = A[N - 1]
	final_max = A[N - 1]
	suffix[N - 1] = A[N - 1]
	for i in range(N - 2, -1, -1):
		curr_max += A[i]
		final_max = max(final_max, curr_max)
		suffix[i] = final_max
	curr_max = A[0]
	final_max = A[0]
	prefix[1] = A[0]
	for i in range(1, N - 1):
		curr_max += A[i]
		final_max = max(final_max, curr_max)
		prefix[i + 1] = final_max
	print(max1[0], end=' ')
	for i in range(1, N):
		fix = max(suffix[i], prefix[i])
		if suffix[i] > 0 and prefix[i] > 0:
			fix = suffix[i] + prefix[i]
		print(max(max1[i], max2[i], fix), end=' ')
	print()