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

There's an array A consisting of N non-zero integers A_{1..N}. A subarray of A is called alternating if any two adjacent elements in it have different signs (i.e. one of them should be negative and the other should be positive).

For each x from 1 to N, compute the length of the longest alternating subarray that starts at x - that is, a subarray A_{x..y} for the maximum possible y ≥ x. The length of such a subarray is y-x+1.

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

The first line of the input contains an integer T - the number of test cases.
The first line of each test case contains N.
The following line contains N space-separated integers A_{1..N}.

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

For each test case, output one line with N space-separated integers - the lengths of the longest alternating subarray starting at x, for each x from 1 to N.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$-10^{9} ≤ A_{i} ≤ 10^{9}$

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

4

1 2 3 4

4

1 -5 1 -5

6

-5 -1 -1 2 -2 -3
----- Sample Output 1 ------ 
1 1 1 1

4 3 2 1

1 1 3 2 1 1
----- explanation 1 ------ 
Example case 1. No two elements have different signs, so any alternating subarray may only consist of a single number.
Example case 2. Every subarray is alternating.
Example case 3. The only alternating subarray of length 3 is A3..5.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split(' ')))
	l1 = [-1 for i in range(a)]
	l1[-1] = 1
	for i in range(a - 2, -1, -1):
		if l[i] >= 0 and l[i + 1] <= 0 or (l[i] <= 0 and l[i + 1] >= 0):
			l1[i] = l1[i + 1] + 1
		else:
			l1[i] = 1
	for i in l1:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	nl = []
	(j, c) = (0, 1)
	for i in range(n):
		if j < i:
			j = i
		while j < n - 1 and (l[j] < 0 and l[j + 1] >= 0 or (l[j] >= 0 and l[j + 1] < 0)):
			j += 1
		print(j - i + 1, end=' ')
	print()


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


def f(arr, n):
	ans = [-1] * n
	ans[n - 1] = 1
	for i in range(n - 2, -1, -1):
		if arr[i] < 0:
			if arr[i + 1] > 0:
				ans[i] = ans[i + 1] + 1
			else:
				ans[i] = 1
		elif arr[i + 1] < 0:
			ans[i] = ans[i + 1] + 1
		else:
			ans[i] = 1
	return ans
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	print(*f(arr, n))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [1] * n
	for i in range(n - 1, 0, -1):
		if arr[i] < 0 and arr[i - 1] < 0 or (arr[i] > 0 and arr[i - 1] > 0):
			continue
		else:
			dp[i - 1] = 1 + dp[i]
	print(*dp)


for _ in range(int(input())):
	n = int(input())
	a = [0 if int(x) < 0 else 1 for x in input().split()]
	(i, j, k) = (0, 0, 0)
	while i <= n - 1:
		s = 0
		j = i
		while j <= n - 1:
			if j < n - 1:
				k = j + 1
			if j == n - 1:
				k = j
			if a[j] != a[k]:
				s += 1
				j += 1
				continue
			if a[j] == a[k]:
				break
		s += 1
		for q in range(s, 0, -1):
			print(q, end=' ')
		i = k
		if j == n - 1:
			break
	print()


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


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


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()] + [0]
	cur = 1
	for i in range(1, n + 1):
		if a[i] * a[i - 1] >= 0:
			while cur:
				print(cur, end=' ')
				cur -= 1
			cur = 1
		else:
			cur += 1
	print()


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	L1 = [-1 for i in range(n)]
	L1[-1] = 1
	for i in range(n - 2, -1, -1):
		if L[i] > 0 and L[i + 1] <= 0 or (L[i] <= 0 and L[i + 1] >= 0):
			L1[i] = L1[i + 1] + 1
		else:
			L1[i] = 1
	for i in L1:
		print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a1 = [-1 for i in range(n)]
	a1[-1] = 1
	for i in range(n - 2, -1, -1):
		if a[i] >= 0 and a[i + 1] <= 0 or (a[i] <= 0 and a[i + 1] >= 0):
			a1[i] = a1[i + 1] + 1
		else:
			a1[i] = 1
	for i in a1:
		print(i, end=' ')
	print()


for i in range(int(input())):
	h = int(input())
	l = list(map(int, input().split(' ')))
	l2 = [-1 for i in range(h)]
	l2[-1] = 1
	for i in range(h - 2, -1, -1):
		if l[i] >= 0 and l[i + 1] <= 0 or (l[i] <= 0 and l[i + 1] >= 0):
			l2[i] = l2[i + 1] + 1
		else:
			l2[i] = 1
	for i in l2:
		print(i, end=' ')
	print()


for j in range(int(input())):
	p = int(input())
	l = list(map(int, input().split(' ')))
	l1 = [-1 for j in range(p)]
	l1[-1] = 1
	for j in range(p - 2, -1, -1):
		if l[j] >= 0 and l[j + 1] <= 0 or (l[j] <= 0 and l[j + 1] >= 0):
			l1[j] = l1[j + 1] + 1
		else:
			l1[j] = 1
	for j in l1:
		print(j, end=' ')
	print()


for i in range(int(input())):
	number = int(input())
	leave = list(map(int, input().split(' ')))
	leave1 = [-1 for i in range(number)]
	leave1[-1] = 1
	for i in range(number - 2, -1, -1):
		if leave[i] >= 0 and leave[i + 1] <= 0 or (leave[i] <= 0 and leave[i + 1] >= 0):
			leave1[i] = leave1[i + 1] + 1
		else:
			leave1[i] = 1
	for i in leave1:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	ints = list(map(int, input().split()))
	ans = [0] * n
	ans[-1] = 1
	j = 0
	while j < n - 1:
		count = 1
		for i in range(j, n - 1):
			if ints[i] < 0:
				if ints[i + 1] > 0:
					count += 1
				else:
					break
			elif ints[i + 1] < 0:
				count += 1
			else:
				break
		itr = count
		while itr > 0:
			ans[j] = itr
			j += 1
			itr -= 1
	print(*ans)