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

There are N minions who are competing in an election of the president of the ACM (Association of Cute Minions). They are standing in a line in the order from minion 1 to minion N. For each i (1 ≤ i ≤ N), the i-th minion has an influence level of S_{i}.

A single minion may cast any number of votes. Minion j will vote for minion i (i ≠ j) if and only if the influence level of the j-th minion is greater than or equal to the sum of influence levels of all the minions standing between them (excluding the i-th and j-th minion).

Your task is to find the number of votes received by each minion.

------ 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 denoting the number of minions.
The second line contains N space-separated integers S_{1}, S_{2}, ..., S_{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 number of votes the i-th minion will get.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ S_{i} ≤ 10^{9} for each valid i$
$sum of N over all test cases won't exceed 10^{6}$

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

Subtask #1 (30 points):

$1 ≤ N ≤ 500$
$sum of N over all test cases won't exceed 10,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
4
4 3 2 1
5
1 2 2 3 1
----- Sample Output 1 ------ 
1 2 3 2
2 3 2 3 1
----- explanation 1 ------ 
Example case 1: 

	The first minion will get only a vote of the second minion.
	The second minion will get votes of the first and third minion.
	The third minion will get votes of the first, second and fourth minion.	
	The fourth minion will get votes of the second and third minion.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Data structures

Complete search
Skill types: Dynamic programming

Sorting

Data structures

Complete search

Starter code:

Solutions:
def leftsearch(prefs, n, l, h, k, i):
	while l <= h:
		m = (l + h) // 2
		if prefs[i - 1] - prefs[m] > k:
			l = m + 1
		elif m > 0:
			if prefs[i - 1] - prefs[m - 1] > k:
				return m
			else:
				h = m - 1
		else:
			return m
	return -1

def rightsearch(prefs, n, l, h, k, i):
	while l <= h:
		m = (l + h) // 2
		if prefs[m] - prefs[i] > k:
			h = m - 1
		elif m < n - 1:
			if prefs[m + 1] - prefs[i] > k:
				return m + 1
			else:
				l = m + 1
		else:
			return m
	return -1

def func(n, arr):
	if n == 1:
		return [0]
	if n == 2:
		return [1, 1]
	prefs = [0] * n
	prefs[0] = arr[0]
	for i in range(1, n):
		prefs[i] = prefs[i - 1] + arr[i]
	l = [0] * n
	for i in range(n):
		if i == 0:
			m2 = rightsearch(prefs, n, i + 1, n - 1, arr[i], i)
			if m2 == -1:
				l[i + 1] += 1
				l[i] -= 1
			else:
				l[m2] += 1
				l[i] -= 1
		elif i == n - 1:
			m1 = leftsearch(prefs, n, 0, i - 1, arr[i], i)
			l[i - 1] += 1
			if m1 > 0:
				l[m1 - 1] -= 1
		else:
			m1 = leftsearch(prefs, n, 0, i - 1, arr[i], i)
			l[i - 1] += 1
			if m1 > 0:
				l[m1 - 1] -= 1
			m2 = rightsearch(prefs, n, i + 1, n - 1, arr[i], i)
			if m2 == -1:
				l[i + 1] += 1
				l[i] -= 1
			else:
				l[m2] += 1
				l[i] -= 1
	suffs = [0] * n
	suffs[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		suffs[i] = suffs[i + 1] + l[i]
	return suffs
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l1 = func(n, arr)
	print(*l1)


for h in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	res = [0] * n
	for i in range(n):
		j = i + 1
		z = 0
		while j < n:
			if s[i] >= z:
				res[j] += 1
				z += s[j]
			else:
				break
			j += 1
		z = 0
		j = i - 1
		while j >= 0:
			if s[i] >= z:
				res[j] += 1
				z += s[j]
			else:
				break
			j -= 1
	print(*res, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	pre = [s[0]]
	for i in range(1, n):
		pre.append(pre[-1] + s[i])
	li = [0] * n
	(li[0], li[-1]) = (1, 1)
	if n == 1:
		print(0)
	else:
		for i in range(1, n - 1):
			li[i] = 2
		for i in range(n):
			for j in range(i + 2, n):
				if pre[j - 1] - pre[i] <= s[i]:
					li[j] += 1
				else:
					break
		for i in range(2, n):
			for j in range(i - 2, -1, -1):
				if pre[i - 1] - pre[j] <= s[i]:
					li[j] += 1
				else:
					break
		for i in li:
			print(i, end=' ')
		print()


t = int(input())
for i in range(t):
	N = int(input())
	minions = [int(i) for i in input().split()]
	votes = [0 for i in range(N)]
	for i in range(N):
		j = i + 1
		z = 0
		while j < N:
			if minions[i] >= z:
				votes[j] += 1
				z += minions[j]
			else:
				break
			j += 1
		j = i - 1
		z = 0
		while j >= 0:
			if minions[i] >= z:
				votes[j] += 1
				z += minions[j]
			else:
				break
			j -= 1
	for i in range(N):
		print(votes[i], end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	v = [0] * n
	for k in range(n):
		t = 0
		for g in range(k + 1, n):
			if s[k] >= t:
				v[g] += 1
				t += s[g]
			else:
				break
		t = 0
		for g in range(k - 1, -1, -1):
			if s[k] >= t:
				v[g] += 1
				t += s[g]
			else:
				break
	print(*v)


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	L = [0] * n
	for j in range(n):
		s = 0
		for k in range(j + 1, n):
			if s <= l[j]:
				L[k] += 1
				s += l[k]
			else:
				break
		s = 0
		for k in range(j - 1, -1, -1):
			if s <= l[j]:
				L[k] += 1
				s += l[k]
			else:
				break
	for j in L:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	minions = list(map(int, input().split()))
	vote = [0] * n
	for i in range(n):
		s = 0
		for j in range(i + 1, n):
			if s <= minions[i]:
				vote[j] += 1
				s += minions[j]
			else:
				break
		s = 0
		for j in range(i - 1, -1, -1):
			if s <= minions[i]:
				vote[j] += 1
				s += minions[j]
			else:
				break
	print(*vote)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = [0] * n
	for j in range(n):
		s = 0
		for k in range(j + 1, n):
			if s <= l[j]:
				m[k] += 1
				s += l[k]
			else:
				break
		s = 0
		for z in range(j - 1, -1, -1):
			if s <= l[j]:
				m[z] += 1
				s += l[z]
			else:
				break
	print(*m)


t = int(input())
for x in range(t):
	n = int(input())
	minions = list(map(int, input().split()))
	votos = [0] * n
	for i in range(n):
		s = 0
		for j in range(i + 1, n):
			if s <= minions[i]:
				votos[j] += 1
				s += minions[j]
			else:
				break
		s = 0
		for j in range(i - 1, -1, -1):
			if s <= minions[i]:
				votos[j] += 1
				s += minions[j]
			else:
				break
	print(*votos)


total = int(input())
for _ in range(total):
	n = int(input())
	minions = [0]
	minions += list(map(int, input().split()))
	votos = [0] * (n + 1)
	popularidad = [0] * (n + 1)
	for i in range(1, n + 1):
		popularidad[i] = popularidad[i - 1] + minions[i]
	for i in range(1, n + 1):
		for j in range(i - 1, 0, -1):
			if minions[i] < popularidad[i - 1] - popularidad[j]:
				break
			votos[j] += 1
		for j in range(i + 1, n + 1):
			if minions[i] < popularidad[j - 1] - popularidad[i]:
				break
			votos[j] += 1
	for i in range(1, n + 1):
		print(votos[i], end=' ')
	print()


T = int(input())
while T:
	n = int(input())
	l = [0]
	l += list(map(int, input().split()))
	v = [0] * (n + 1)
	s = [0] * (n + 1)
	for i in range(1, n + 1):
		s[i] = s[i - 1] + l[i]
	for i in range(1, n + 1):
		for j in range(i - 1, 0, -1):
			if l[i] < s[i - 1] - s[j]:
				break
			v[j] += 1
		for j in range(i + 1, n + 1):
			if l[i] < s[j - 1] - s[i]:
				break
			v[j] += 1
	for i in range(1, n + 1):
		print(v[i], end=' ')
	print()
	T = T - 1


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	Answer = [0] * n
	for i in range(0, n):
		j = i + 1
		x = 0
		while j < n:
			if arr1[i] >= x:
				Answer[j] += 1
				x += arr1[j]
			else:
				break
			j += 1
		x = 0
		j = i - 1
		while j >= 0:
			if arr1[i] >= x:
				Answer[j] += 1
				x += arr1[j]
			else:
				break
			j -= 1
	print(*Answer, end=' ')
	print()


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	for i in range(n):
		sumx = 0
		for j in range(i + 1, n):
			if sumx <= a[i]:
				b[j] += 1
				sumx += a[j]
			else:
				break
		sumx = 0
		for j in range(i - 1, -1, -1):
			if sumx <= a[i]:
				b[j] += 1
				sumx += a[j]
			else:
				break
	print(' '.join(map(str, b)))


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def solution(li):
	pre = []
	s = 0
	for i in range(len(li)):
		s += li[i]
		pre.append(s)
	vote = [0] * len(li)
	for i in range(len(li)):
		if i != len(li) - 1:
			mid = bisect_right(pre, pre[i] + li[i], i + 1, len(li))
			vote[mid if mid < len(li) else len(li) - 1] += 1
			vote[i] -= 1
		if i != 0:
			mid = bisect_left(pre, pre[i - 1] - li[i], 0, i)
			vote[i - 1] += 1
			if mid - 1 >= 0:
				vote[mid - 1] -= 1
	i = len(li) - 2
	while i >= 0:
		vote[i] += vote[i + 1]
		i -= 1
	return vote

def input_test():
	for _ in range(int(input())):
		n = int(input())
		li = list(map(int, input().strip().split(' ')))
		out = solution(li)
		print(' '.join(list(map(str, out))))
input_test()


def minvote(arr, n):
	from bisect import bisect_left, bisect_right
	prefix_sum = [arr[i] for i in range(n)]
	votes = [0 for i in range(n + 1)]
	for i in range(1, n):
		prefix_sum[i] = prefix_sum[i - 1] + arr[i]
	for i in range(n):
		left = bisect_left(prefix_sum, prefix_sum[i - 1] - arr[i], lo=0, hi=i)
		right = bisect_right(prefix_sum, prefix_sum[i] + arr[i], lo=i + 1, hi=n)
		if i != 0:
			votes[left] += 1
			votes[i] -= 1
		if i != n - 1:
			votes[i + 1] += 1
			votes[right + 1 if right + 1 <= n else n] -= 1
	for i in range(1, n):
		votes[i] += votes[i - 1]
	return ' '.join(map(str, votes[:-1]))
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(minvote(arr, n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	re = [0] * n
	for i in range(len(a)):
		s = 0
		for j in range(i + 1, len(a)):
			if a[i] >= s:
				s += a[j]
				re[j] += 1
			else:
				break
	a.reverse()
	for i in range(len(a)):
		s = 0
		for j in range(i + 1, len(a)):
			if a[i] >= s:
				s += a[j]
				re[len(a) - 1 - j] += 1
			else:
				break
	for i in re:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	votes = [0] * n
	for voter in range(n):
		sm = 0
		for cand1 in range(voter + 1, n):
			if sm <= l[voter]:
				votes[cand1] += 1
			else:
				break
			sm += l[cand1]
		sm = 0
		for cand2 in range(voter - 1, -1, -1):
			if sm <= l[voter]:
				votes[cand2] += 1
			else:
				break
			sm += l[cand2]
	print(*votes)


from sys import stdin
t = int(stdin.readline())
while t != 0:
	n = int(stdin.readline())
	inp = list(map(int, stdin.readline().split()))
	v = [0] * n
	for i in range(n):
		sum1 = 0
		sum2 = 0
		if i + 1 < n:
			v[i + 1] += 1
		if i - 1 >= 0:
			v[i - 1] += 1
		for j in range(i - 1, -1, -1):
			sum2 = sum2 + inp[j]
			if j - 1 >= 0 and sum2 <= inp[i]:
				v[j - 1] += 1
			else:
				break
		for j in range(i + 1, n):
			sum1 = sum1 + inp[j]
			if sum1 <= inp[i] and j + 1 < n:
				v[j + 1] += 1
			else:
				break
	for i in range(n):
		print(v[i], end=' ')
	print('')
	t = t - 1


t = int(input())
while t != 0:
	n = int(input())
	inp = list(map(int, input().split()))
	v = [0] * n
	for i in range(n):
		sum1 = 0
		sum2 = 0
		if i + 1 < n:
			v[i + 1] += 1
		if i - 1 >= 0:
			v[i - 1] += 1
		for j in range(i - 1, -1, -1):
			sum2 = sum2 + inp[j]
			if j - 1 >= 0 and sum2 <= inp[i]:
				v[j - 1] += 1
			else:
				break
		for j in range(i + 1, n):
			sum1 = sum1 + inp[j]
			if sum1 <= inp[i] and j + 1 < n:
				v[j + 1] += 1
			else:
				break
	for i in range(n):
		print(v[i], end=' ')
	print('')
	t = t - 1


res = []

def getSum(nums, sums, i, j):
	if j > i:
		return sums[j] - nums[j] - sums[i]
	elif i > j:
		return sums[i] - nums[i] - sums[j]
	else:
		return 0
for _ in range(0, int(input())):
	n = input()
	nums = list(map(int, input().split(' ')))
	sums = [0] * len(nums)
	sums[0] = nums[0]
	for k in range(1, len(nums)):
		sums[k] = sums[k - 1] + nums[k]
	votes = [0] * len(nums)
	for j in range(0, len(nums)):
		for i in range(j + 1, len(nums)):
			if getSum(nums, sums, j, i) > nums[j]:
				break
			votes[i] += 1
		for i in range(j - 1, -1, -1):
			if getSum(nums, sums, i, j) > nums[j]:
				break
			votes[i] += 1
	vote = ''
	for v in votes:
		vote += ' ' + str(v)
	res.append(vote.lstrip())
for xx in res:
	print(xx)


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	a = [int(x) for x in input().strip().split(' ')]
	w = [0] * n
	for j in range(n - 1):
		s = 0
		for k in range(j + 1, n):
			if s <= a[j]:
				w[k] += 1
				s += a[k]
			else:
				break
	for i in range(n - 1, 0, -1):
		s = 0
		for j in range(i - 1, -1, -1):
			if s <= a[i]:
				w[j] += 1
				s += a[j]
			else:
				break
	for i in w:
		print(i, end=' ')
	print()


def dfs(root):
	vis[root] = 1
	print(root)
	for i in edge[root]:
		if not vis[i]:
			dfs(i)
	return

def main():
	t = 1
	while t:
		t = int(input())
		while t:
			n = int(input())
			a = list(map(int, input().strip().split()))
			sum = [0] * n
			t -= 1
			sum[0] = a[0]
			votes = [0] * n
			for i in range(1, n):
				sum[i] = sum[i - 1] + a[i]
			for j in range(n):
				for i in range(j + 1, n):
					if abs(sum[i] - sum[j] - a[i]) > a[j]:
						break
					votes[i] += 1
				for i in range(j - 1, -1, -1):
					if abs(sum[j] - sum[i] - a[j]) > a[j]:
						break
					votes[i] += 1
			print(' '.join(map(str, votes)))
main()


from itertools import accumulate
from bisect import bisect_left, bisect_right
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = list(accumulate(a))
	res = [0] * (n + 2)
	for (i, (x, y)) in enumerate(zip(s, a)):
		l = bisect_left(s, x - 2 * y, 0, i)
		res[l] += 1
		r = bisect_right(s, x + y, i + 1)
		res[r + 1] -= 1
	print(*(x - 1 for x in accumulate(res[:n])))


import sys
import copy

def read(typ=str):
	return list(map(typ, sys.stdin.readline().split()))
test = int(input())
for _ in range(test):
	n = int(input())
	arr = [int(x) for x in input().strip().split()]
	temp = [0 for _ in range(n)]
	sumF = 0
	sumB = 0
	(sumF, sumB) = (0, 0)
	for i in range(n - 1):
		sumF = 0
		for j in range(i + 1, n):
			if arr[i] >= sumF:
				temp[j] += 1
				sumF += arr[j]
			else:
				break
	for i in range(n - 1, 0, -1):
		sumB = 0
		for j in range(i - 1, -1, -1):
			if arr[i] >= sumB:
				temp[j] += 1
				sumB += arr[j]
			else:
				break
	temp = map(str, temp)
	print(' '.join(temp))


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = [0] * n
	for j in range(0, n):
		s1 = 0
		for k in range(j + 1, n):
			if s1 <= a[j]:
				s1 += a[k]
				b[k] += 1
			else:
				break
		s1 = 0
		for k in range(j - 1, -1, -1):
			if s1 <= a[j]:
				s1 += a[k]
				b[k] += 1
			else:
				break
	print(' '.join(map(str, b)))


T = int(input())
for t in range(T):
	n = int(input())
	s = list(map(int, input().split()))
	minvote = [0] * n
	for i in range(n):
		sum = 0
		for j in range(i + 1, n):
			if sum > s[i]:
				break
			else:
				sum += s[j]
				minvote[j] += 1
		sum = 0
		for k in range(i - 1, -1, -1):
			if sum > s[i]:
				break
			else:
				sum += s[k]
				minvote[k] += 1
	print(*minvote)


for _ in range(int(input())):
	N = int(input())
	S = list(map(int, input().split()))
	t = [0] * N
	if N == 1:
		print('0')
	else:
		s = [0] * N
		for i in range(0, N):
			sum = 0
			for j in range(i + 1, N):
				if sum <= S[i]:
					s[j] += 1
					sum += S[j]
				else:
					break
			sum = 0
			for j in range(i - 1, -1, -1):
				if sum <= S[i]:
					s[j] += 1
					sum += S[j]
				else:
					break
		print(*s)


def problem3(n, list):
	Graph = [0] * n
	for i in range(n):
		diff = 0
		for j in range(i - 1, -1, -1):
			if list[i] >= diff:
				Graph[j] += 1
				diff = diff + list[j]
			else:
				break
	for i in range(n):
		diff = 0
		for j in range(i + 1, n):
			if list[i] >= diff:
				Graph[j] += 1
				diff = diff + list[j]
			else:
				break
	print(*Graph)
test = int(input())
for i in range(test):
	n = int(input())
	l = list(map(int, input().split()))
	problem3(n, l)


from collections import defaultdict as dd
from itertools import permutations as pp
from math import *
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	left = 0
	right = 0
	lk = [0] * (n + 1)
	for i in range(1, n + 1):
		lk[i] = lk[i - 1] + a[i - 1]
	b = a[::-1]
	rk = [0] * (n + 1)
	for i in range(1, n + 1):
		rk[i] = rk[i - 1] + b[i - 1]
	ans = [0] * (n + 2)
	for i in range(n):
		st = br(lk, a[i] + lk[i + 1], i + 1, n + 1)
		if st == n + 1:
			st = st - 1
		ans[i + 1] += 1
		ans[st] += -1
	for i in range(n):
		st = br(rk, b[i] + rk[i + 1], i + 1, n + 1)
		if st == n + 1:
			st -= 1
		ans[n - st] += 1
		ans[n - i - 1] -= 1
	for i in range(n + 2):
		ans[i] += ans[i - 1]
	print(*ans[:-2])


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	rev = list(reversed(arr))
	vote = [2] * n
	vote[0] -= 1
	vote[n - 1] -= 1
	for j in range(n - 2):
		summ = 0
		for k in range(j + 2, n):
			summ += arr[k - 1]
			if summ <= arr[j]:
				vote[k] += 1
			else:
				break
		summ = 0
		for k in range(j + 2, n):
			summ += rev[k - 1]
			if summ <= rev[j]:
				vote[n - 1 - k] += 1
			else:
				break
	print(*vote)


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split(' ')))
	vote = [0] * n
	for i in range(n):
		sum1 = 0
		sum2 = 0
		for j in range(i - 1, -1, -1):
			if sum2 <= s[i]:
				vote[j] += 1
				sum2 += s[j]
			else:
				break
		for j in range(i + 1, n):
			if sum1 <= s[i]:
				vote[j] += 1
				sum1 += s[j]
			else:
				break
	for num in vote:
		print(num, end=' ')
	print('')


T = int(input())
for t in range(0, T):
	N = int(input())
	S = list(map(int, input().split(' ')))
	votes = [0] * N
	for i in range(N):
		forward = 0
		backward = 0
		for j in range(i - 1, -1, -1):
			if backward <= S[i]:
				votes[j] += 1
				backward += S[j]
			else:
				break
		for j in range(i + 1, N):
			if forward <= S[i]:
				votes[j] += 1
				forward += S[j]
			else:
				break
	for v in votes:
		print(v, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	vote = [0] * n
	for i in range(n):
		fs = 0
		for j in range(i - 1, -1, -1):
			if fs > a[i]:
				break
			else:
				fs += a[j]
				vote[j] += 1
		bs = 0
		for k in range(i + 1, n):
			if bs > a[i]:
				break
			else:
				bs += a[k]
				vote[k] += 1
	print(*vote)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = [0] * n
	s[0] = a[0]
	for j in range(1, n):
		s[j] = s[j - 1] + a[j]
	ans = [0] * n
	for j in range(n):
		k = j + 1
		while k < n:
			if a[j] >= s[k - 1] - s[j]:
				ans[k] = ans[k] + 1
				k += 1
			else:
				break
		k = j - 1
		while k >= 0:
			if a[j] >= s[j - 1] - s[k]:
				ans[k] += 1
				k -= 1
			else:
				break
	for j in range(n):
		print(ans[j], end=' ')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	w = [0] * n
	for j in range(n - 1):
		sum1 = 0
		for k in range(j + 1, n):
			if sum1 <= a[j]:
				w[k] += 1
				sum1 += a[k]
			else:
				break
	for j in range(n - 1, 0, -1):
		sum1 = 0
		for k in range(j - 1, -1, -1):
			if sum1 <= a[j]:
				w[k] += 1
				sum1 += a[k]
			else:
				break
	print(' '.join((str(y) for y in w)))


y = int(input())
number = [0 for P in range(y)]
s = [[] for Q in range(y)]
for I in range(y):
	number[I] = int(input())
	l = input().split()
	for a in range(number[I]):
		s[I].append(int(l[a]))
v = [[] for R in range(y)]
for I in range(y):
	if number[I] > 1:
		v[I].append(1)
		for D in range(1, number[I] - 1):
			v[I].append(2)
		v[I].append(1)
	else:
		print(0)
		continue
	for k in range(2, number[I]):
		sumx = 0
		for M in range(k - 1, 0, -1):
			sumx += s[I][M]
			if sumx > s[I][k]:
				break
			v[I][M - 1] += 1
	for k in range(0, number[I] - 2):
		sumx = 0
		for M in range(k + 1, number[I] - 1):
			sumx += s[I][M]
			if sumx > s[I][k]:
				break
			v[I][M + 1] += 1
	for y in v[I]:
		print(y, end=' ')
	print('')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	v = [0] * n
	for i in range(n):
		s1 = 0
		s2 = 0
		if i + 1 < n:
			v[i + 1] += 1
		if i - 1 >= 0:
			v[i - 1] += 1
		for j in range(i + 1, n):
			s1 = s1 + a[j]
			if s1 <= a[i] and j + 1 < n:
				v[j + 1] += 1
			else:
				break
		for j in range(i - 1, -1, -1):
			s2 = s2 + a[j]
			if s2 <= a[i] and j - 1 >= 0:
				v[j - 1] += 1
			else:
				break
	for i in range(n):
		print(v[i], end=' ')
	print()
	t = t - 1


t = int(input().strip())
while t:
	n = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	b = [0] * n
	for i in range(n):
		inf = a[i]
		j = i + 1
		while inf >= 0 and i != n - 1 and (j < n):
			b[j] += 1
			inf -= a[j]
			j += 1
		inf = a[i]
		j = i - 1
		while inf >= 0 and i and (j >= 0):
			b[j] += 1
			inf -= a[j]
			j -= 1
	for x in b:
		print(x, end=' ')
	print()
	t -= 1


tst = int(input())
st = []
d = 0
for x in range(0, tst):
	num = int(input())
	arr = [int(y) for y in input().split(' ')]
	lst = []
	n = 0
	for i in range(0, num):
		lst.append(n)
	for j in range(0, len(arr)):
		cnt = 0
		for k in range(j + 1, len(arr), 1):
			if arr[j] >= cnt:
				lst[k] += 1
			else:
				break
			cnt += arr[k]
		b = 0
		if j > 0:
			for i in range(j - 1, -1, -1):
				if arr[j] >= b:
					lst[i] += 1
				else:
					break
				b += arr[i]
	for i in range(0, len(lst)):
		print(lst[i], end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	for (i, ele) in enumerate(arr):
		dist = -ele
		for j in range(i, 0, -1):
			dist += arr[j]
			if dist > ele:
				break
			else:
				ans[j - 1] += 1
		dist = -ele
		for j in range(i, n - 1, +1):
			dist += arr[j]
			if dist > ele:
				break
			else:
				ans[j + 1] += 1
	print(*ans)


n = int(input())
r = []
q = []
a = []
p = []
for i in range(0, n):
	d = int(input())
	a.append(d)
	p = [int(x) for x in input().split(' ')]
	q.append(p)
x = 0
for i in range(0, n):
	u = []
	m = 0
	for o in range(0, a[i]):
		u.append(m)
	for j in range(0, len(q[i])):
		s = 0
		for k in range(j + 1, len(q[i]), 1):
			if q[i][j] >= s:
				u[k] = u[k] + 1
			else:
				break
			s = s + q[i][k]
		s1 = 0
		if j > 0:
			for k in range(j - 1, -1, -1):
				if q[i][j] >= s1:
					u[k] = u[k] + 1
				else:
					break
				s1 = s1 + q[i][k]
	r.append(u)
for i in range(0, len(r)):
	for j in range(0, len(r[i])):
		print(r[i][j], end=' ')
	print()


N = 5
s = ['1', '2', '2', '3', '1']
import numpy as np
import bisect
from operator import add

def add1(arr, N, lo, hi, val):
	arr[lo] += val
	if hi != N - 1:
		arr[hi + 1] -= val
	return arr

def updateArray(arr, N):
	for i in range(1, N):
		arr[i] += arr[i - 1]
	return arr

def chef(N, s):
	s = list(map(int, s))
	prefix = [0] * N
	suffix = [0] * N
	p1 = 0
	s1 = 0
	for i in range(0, N):
		p1 += s[i]
		prefix[i] = p1
		s1 += s[N - i - 1]
		suffix[i] = s1
	right = [0] * N
	left = [0] * N
	for i in range(0, N):
		key = prefix[i] + s[i]
		x = bisect.bisect_right(prefix, key)
		if x > N - 1:
			x = N - 1
		right[i] = x
	for i in range(0, N):
		key = suffix[i] + s[N - i - 1]
		x = bisect.bisect_right(suffix, key)
		if x > N - 1:
			x = N - 1
		left[i] = N - x - 1
	left.reverse()
	ans = [0] * N
	for i in range(0, N):
		add1(ans, N, left[i], right[i], 1)
	updateArray(ans, N)
	for i in range(0, N):
		ans[i] -= 1
	str2 = ' '.join((str(x) for x in ans))
	return str2
T = int(input())
outputs = []
for i in range(0, T):
	N = int(input())
	s = input().split()
	ans = chef(N, s)
	outputs.append(ans)
for i in outputs:
	print(i)


n = int(input())
for i in range(0, n):
	a = int(input())
	p = [int(x) for x in input().split(' ')]
	l = []
	m = 0
	for i in range(0, a):
		l.append(m)
	for j in range(0, len(p)):
		s = 0
		for k in range(j + 1, len(p), 1):
			if p[j] >= s:
				l[k] = l[k] + 1
			else:
				break
			s = s + p[k]
		s1 = 0
		if j > 0:
			for k in range(j - 1, -1, -1):
				if p[j] >= s1:
					l[k] = l[k] + 1
				else:
					break
				s1 = s1 + p[k]
	for i in range(0, len(l)):
		print(l[i], end=' ')
	print()


T = int(input())
N = [0 for p in range(T)]
S = [[] for q in range(T)]
for i in range(T):
	N[i] = int(input())
	l = input().split()
	for j in range(N[i]):
		S[i].append(int(l[j]))
V = [[] for r in range(T)]
for i in range(T):
	if N[i] > 1:
		V[i].append(1)
		for d in range(1, N[i] - 1):
			V[i].append(2)
		V[i].append(1)
	else:
		print(0)
		continue
	for k in range(2, N[i]):
		sumy = 0
		for m in range(k - 1, 0, -1):
			sumy += S[i][m]
			if sumy > S[i][k]:
				break
			V[i][m - 1] += 1
	for k in range(0, N[i] - 2):
		sumy = 0
		for m in range(k + 1, N[i] - 1):
			sumy += S[i][m]
			if sumy > S[i][k]:
				break
			V[i][m + 1] += 1
	for t in V[i]:
		print(t, end=' ')
	print('')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n - 1):
		s = 0
		for j in range(i + 1, n):
			if s <= a[i]:
				ans[j] += 1
			else:
				break
			s += a[j]
	for i in range(n - 1, -1, -1):
		s = 0
		for j in range(i - 1, -1, -1):
			if s <= a[i]:
				ans[j] += 1
			else:
				break
			s += a[j]
	print(*ans)


testcase = int(input())
for tests in range(testcase):
	n = int(input())
	lst = list(map(int, input().split()))
	final_lst = [0 for i in range(n)]
	for i in range(n):
		p = 0
		for k in range(i + 1, n):
			p += lst[k]
			if p - lst[k] <= lst[i]:
				final_lst[k] += 1
			else:
				break
		p = 0
		for j in range(i - 1, -1, -1):
			p += lst[j]
			if p - lst[j] <= lst[i]:
				final_lst[j] += 1
			else:
				break
	for m in final_lst:
		print(m, end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().strip().split()))
	vote = [0 for i in range(n)]
	for i in range(n):
		influence = 0
		voting = s[i]
		for j in range(i + 1, n):
			if voting >= influence:
				vote[j] += 1
			else:
				break
			influence += s[j]
		influence = 0
		for j in range(i - 1, -1, -1):
			if voting >= influence:
				vote[j] += 1
			else:
				break
			influence += s[j]
	print(' '.join([str(i) for i in vote]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.insert(0, 0)
	prefix = [0] * 100010
	suffix = [0] * 100010
	for i in range(1, n):
		total = 0
		for j in range(i + 1, n + 1):
			total += l[j]
			if total > l[i]:
				break
		prefix[i + 1] += 1
		prefix[j + 1] -= 1
	for i in range(n, 1, -1):
		total = 0
		for j in range(i - 1, 0, -1):
			total += l[j]
			if total > l[i]:
				break
		suffix[i] -= 1
		suffix[j] += 1
	for i in range(1, n + 1):
		prefix[i] += prefix[i - 1]
		suffix[i] += suffix[i - 1]
		print(prefix[i] + suffix[i], end=' ')
	print()


t = int(input())
while t:
	n = int(input())
	arr = [int(i) for i in input().split()]
	br = [0] * (n + 1)
	for i in range(n):
		sums = 0
		for j in range(i + 1, n):
			if sums <= arr[i]:
				br[j] += 1
			else:
				break
			sums += arr[j]
	for i in range(n - 1, -1, -1):
		sums = 0
		for j in range(i - 1, -1, -1):
			if sums <= arr[i]:
				br[j] += 1
			else:
				break
			sums += arr[j]
	for i in range(n):
		print(br[i], end=' ')
	print()
	t -= 1


import sys
import math
t = int(input())
for _ in range(t):
	n = int(input())
	c = [0] * n
	a = list(map(int, input().split()))
	for i in range(n):
		s = 0
		for j in range(i + 1, n):
			if a[i] >= s:
				s += a[j]
				c[j] += 1
			else:
				break
		s = 0
		for j in range(i - 1, -1, -1):
			if a[i] >= s:
				s += a[j]
				c[j] += 1
			else:
				break
	for j in range(0, n):
		print(c[j], end=' ')
	print()


T = int(input())
for cases in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	votes = []
	for i in range(N):
		votes.append(0)
	s = ''
	for i in range(N):
		c = 0
		for j in range(i + 1, N):
			if c <= A[i]:
				votes[j] += 1
			else:
				break
			c += A[j]
		c = 0
		for j in range(i - 1, -1, -1):
			if c <= A[i]:
				votes[j] += 1
			else:
				break
			c += A[j]
	for i in range(N):
		s += str(votes[i]) + ' '
	print(s)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	vote = [0] * N
	cs = list()
	sum = 0
	for x in A:
		sum = sum + x
		cs.append(sum)
	for i in range(N):
		for j in range(i - 1, -1, -1):
			if cs[i - 1] - cs[j] <= A[i]:
				vote[j] += 1
			else:
				break
		for j in range(i + 1, N):
			if cs[j - 1] - cs[i] <= A[i]:
				vote[j] += 1
			else:
				break
	print(*vote)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n >= 2:
		y = [2] * n
		y[0] = 1
		y[n - 1] = 1
		for k in range(0, n - 2):
			sum = 0
			for l in range(k + 1, n - 1):
				sum += a[l]
				if sum <= a[k]:
					y[l + 1] += 1
				else:
					break
		for m in range(n - 1, 1, -1):
			sum = 0
			for o in range(m - 1, 0, -1):
				sum += a[o]
				if sum <= a[m]:
					y[o - 1] += 1
				else:
					break
		print(*y)
	else:
		print(0)


def left_traversal(i, A, prefix, count_list):
	low = 0
	high = i - 1
	if A[i] >= prefix[i - 1] - prefix[low]:
		count_list[low] += 1
		count_list[i] -= 1
		return count_list
	elif A[i] < A[i - 1]:
		count_list[high] += 1
		count_list[i] -= 1
		return count_list
	else:
		curr_pos = high
		while low < high:
			mid = (low + high) // 2
			if A[i] >= prefix[i - 1] - prefix[mid]:
				if mid < curr_pos:
					curr_pos = mid
				high = mid
			else:
				low = mid + 1
		count_list[curr_pos] += 1
		count_list[i] -= 1
	return count_list

def right_traversal(i, A, prefix, count_list, N):
	low = i + 1
	high = N - 1
	if A[i] >= prefix[high - 1] - prefix[i]:
		count_list[low] += 1
		return count_list
	elif A[i] < A[i + 1]:
		count_list[i + 1] += 1
		count_list[i + 2] -= 1
		return count_list
	else:
		curr_pos = low
		while low < high:
			mid = (low + high) // 2
			if A[i] >= prefix[mid - 1] - prefix[i]:
				if mid > curr_pos:
					curr_pos = mid
					low = mid + 1
			else:
				high = mid
		count_list[curr_pos + 1] -= 1
		count_list[i + 1] += 1
	return count_list
T = int(input())
for eachtestcase in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	prefix = [A[0]]
	count_list = [0] * N
	for i in range(1, N):
		prefix.append(prefix[i - 1] + A[i])
	for i in range(1, N):
		count_list = left_traversal(i, A, prefix, count_list)
	for i in range(N - 1):
		count_list = right_traversal(i, A, prefix, count_list, N)
	numvotes = [count_list[0]]
	for i in range(1, N):
		numvotes.append(numvotes[i - 1] + count_list[i])
	print(*numvotes, sep=' ')


def leftup(i, S, prefix, count):
	left = 0
	right = i - 1
	if S[i] >= prefix[i - 1] - prefix[left]:
		count[left] += 1
		count[i] -= 1
		return count
	elif S[i] < S[i - 1]:
		count[right] += 1
		count[i] -= 1
		return count
	else:
		pos = right
		while left < right:
			mid = (left + right) // 2
			if S[i] >= prefix[i - 1] - prefix[mid]:
				if mid < pos:
					pos = mid
				right = mid
			else:
				left = mid + 1
		count[pos] += 1
		count[i] -= 1
	return count

def rightup(i, S, prefix, count, N):
	left = i + 1
	right = N - 1
	if S[i] >= prefix[right - 1] - prefix[i]:
		count[left] += 1
		return count
	elif S[i] < S[i + 1]:
		count[i + 1] += 1
		count[i + 2] -= 1
		return count
	else:
		pos = left
		while left < right:
			mid = (left + right) // 2
			if S[i] >= prefix[mid - 1] - prefix[i]:
				if mid > pos:
					pos = mid
				left = mid + 1
			else:
				right = mid
		count[pos + 1] -= 1
		count[i + 1] += 1
		return count
T = int(input())
for testCase in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	prefix = [S[0]]
	for i in range(1, N):
		prefix.append(prefix[i - 1] + S[i])
	count = [0] * N
	for i in range(1, N):
		count = leftup(i, S, prefix, count)
	for i in range(N - 1):
		count = rightup(i, S, prefix, count, N)
	votes = [count[0]]
	for i in range(1, N):
		votes.append(votes[i - 1] + count[i])
	print(*votes, sep=' ')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if n == 1:
		print('0')
	elif n == 2:
		print('1 1')
	else:
		co = [0] * n
		for j in range(n):
			(cs, k) = (0, j + 1)
			while k < n and cs <= s[j]:
				co[k] += 1
				cs += s[k]
				k += 1
			(cs, k) = (0, j - 1)
			while k >= 0 and cs <= s[j]:
				co[k] += 1
				cs += s[k]
				k -= 1
		for j in range(n):
			print(co[j], end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	influences = list(map(int, input().split()))
	rev_infl = list(reversed(influences[:]))
	sums = influences[:]
	rsums = rev_infl
	for i in range(1, n):
		sums[i] += sums[i - 1]
		rsums[i] += rsums[i - 1]
	votes = [0] * n
	for i in range(0, n - 1):
		j = i + 1
		while j < n and sums[j - 1] - sums[i] <= influences[i]:
			votes[j] += 1
			j += 1
		u = n - 1 - i
		v = u - 1
		while v >= 0 and sums[u - 1] - sums[v] <= influences[u]:
			votes[v] += 1
			v -= 1
	print(' '.join(map(str, votes)))


t = int(input())
for z in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	CurrSum = 0
	Ci = 0
	AnsArray = [0] * n
	AnsArray[0] = 1
	for i in range(n - 1):
		CurrSum = 0
		Ci = i + 1
		while CurrSum <= s[i] and Ci < n:
			CurrSum += s[Ci]
			Ci += 1
		if Ci < n:
			AnsArray[Ci] -= 1
	s = s[::-1]
	for i in range(n - 1):
		CurrSum = 0
		Ci = i + 1
		while CurrSum <= s[i] and Ci < n:
			CurrSum += s[Ci]
			Ci += 1
		AnsArray[n - Ci] += 1
	for i in range(1, n):
		AnsArray[i] += AnsArray[i - 1]
	print(' '.join((str(x - 1) for x in AnsArray)))


for _ in range(int(input())):
	N = int(input())
	s = list(map(int, input().split()))
	v = [0] * N
	for i in range(N):
		inf = 0
		j = i + 1
		while j < N and s[i] >= inf:
			v[j] += 1
			inf += s[j]
			j += 1
	for i in range(N - 1, -1, -1):
		inf = 0
		j = i - 1
		while j >= 0 and s[i] >= inf:
			v[j] += 1
			inf += s[j]
			j -= 1
	for i in v:
		print(i, end=' ')


def forward(array, index, vote_array):
	sum = 0
	j = index + 1
	size = len(array)
	vote_array[j] += 1
	while j < size - 1:
		sum += array[j]
		if sum <= array[index]:
			j += 1
			vote_array[j] += 1
		else:
			break

def reverse(array, index, vote_array):
	sum = 0
	j = index - 1
	vote_array[j] += 1
	while j > 0:
		sum += array[j]
		if sum <= array[index]:
			j -= 1
			vote_array[j] += 1
		else:
			break
T = int(input())
for i in range(T):
	N = int(input())
	si = list(map(int, input().split()))
	vote_array = []
	for j in range(N):
		vote_array.append(0)
	if N == 1:
		pass
	else:
		for j in range(N):
			if j == 0:
				forward(si, j, vote_array)
			elif j == N - 1:
				reverse(si, j, vote_array)
			else:
				forward(si, j, vote_array)
				reverse(si, j, vote_array)
	for i in range(N):
		print(str(vote_array[i]) + ' ', end='')
print()


def findRight(preSum, L, R, val):
	while L < R:
		M = (L + R + 1) // 2
		if preSum[M] <= val:
			L = M
		else:
			R = M - 1
	return L

def handle(nums):
	n = len(nums)
	votes = [0] * n
	preSum = [0] * (n + 1)
	for (i, k) in enumerate(nums):
		preSum[i + 1] = preSum[i] + k
	speed = [0] * (n + 1)
	for i in range(n - 2, -1, -1):
		if nums[i] < nums[i + 1]:
			j = i + 1
		else:
			j = findRight(preSum, i + 1, n - 1, nums[i] + preSum[i + 1])
		speed[i + 1] += 1
		speed[j + 1] -= 1
	sd = 0
	for i in range(n):
		sd += speed[i]
		votes[i] += sd
	return votes

def solve():
	N = int(input())
	nums = list(map(int, input().split()))
	votes = [0] * N
	votes1 = handle(nums)
	votes2 = handle(nums[::-1])[::-1]
	votes = map(sum, zip(votes1, votes2))
	print(' '.join(map(str, votes)))
T = int(input())
for _ in range(T):
	solve()


import bisect

def main(a, n):
	prefix_left = [0 for x in range(n)]
	prefix_left[0] = a[0]
	for i in range(1, len(a)):
		prefix_left[i] = prefix_left[i - 1] + a[i]
	votes_left = [0 for x in range(n)]
	for i in range(0, n - 1):
		L = i + 1
		R = bisect.bisect_right(prefix_left, a[i] + prefix_left[i])
		votes_left[L] += 1
		if R < n - 1:
			votes_left[R + 1] -= 1
	for i in range(1, n):
		votes_left[i] += votes_left[i - 1]
	prefix_right = [0 for x in range(n)]
	prefix_right[n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		prefix_right[i] = prefix_right[i + 1] + a[i]
	votes_right = [0 for x in range(n)]
	prefix_right.reverse()
	for i in range(0, n - 1):
		R = bisect.bisect_right(prefix_right, a[n - 1 - i] + prefix_right[i])
		L = i + 1
		votes_right[L] += 1
		if R < n - 1:
			votes_right[R + 1] -= 1
	for i in range(1, n):
		votes_right[i] += votes_right[i - 1]
	votes_right.reverse()
	print(' '.join((str(votes_left[x] + votes_right[x]) for x in range(0, n))))
T = int(input())
while T:
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	main(a, n)
	T -= 1


test = int(input())
while test > 0:
	test -= 1
	n = int(input())
	l = list(map(int, input().split()))
	data = []
	curr = 0
	for x in l:
		curr += x
		data += [curr]
	count = [0] * n
	i = 0
	while i < n:
		j = i + 1
		while l[i] >= data[j - 1] - data[i] and j < n:
			count[j] += 1
			j += 1
		j = i - 1
		while l[i] >= data[i - 1] - data[j] and j >= 0:
			count[j] += 1
			j -= 1
		i += 1
	print(' '.join(map(str, count)))


for i in range(int(input())):
	(n, lst) = (int(input()), list(map(int, input().split())))
	(p, l2) = (0, [])
	for i in lst:
		p += i
		l2.append(p)
	t = [0 for i in range(n)]
	for j in range(n):
		p = 0
		for k in range(j - 1, -1, -1):
			p += lst[k]
			if p - lst[k] <= lst[j]:
				t[k] += 1
			else:
				break
		p = 0
		for l in range(j + 1, n):
			p += lst[l]
			if p - lst[l] <= lst[j]:
				t[l] += 1
			else:
				break
	for m in t:
		print(m, end=' ')
	print()


t = int(input())
for j in range(t):
	s = int(input())
	a = []
	b = []
	s1 = [0]
	for j in input().split():
		a.append(int(j))
		b.append(0)
		s1.append(s1[-1] + a[-1])
	del s1[0]
	for j in range(0, s):
		for i in range(j + 1, s):
			if a[j] >= s1[i] - s1[j] - a[i]:
				b[i] += 1
			else:
				break
	for j in range(s - 1, 0, -1):
		for j1 in range(j - 1, -1, -1):
			if a[j] >= s1[j] - s1[j1] - a[j]:
				b[j1] += 1
			else:
				break
	for i in b:
		print(i, end=' ')
	print('')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [0] * n
	for i in range(n):
		s1 = 0
		for j in range(i + 1, n):
			if s1 <= a[i]:
				s1 += a[j]
				b[j] += 1
			else:
				break
		s1 = 0
		for j in range(i - 1, -1, -1):
			if s1 <= a[i]:
				s1 += a[j]
				b[j] += 1
			else:
				break
	for i in range(n):
		print(b[i], end=' ')
	print(' ')