Read problem statements in [Russian], [Bengali], and [Mandarin Chinese] as well.

There are $N$ students standing in a canteen queue, numbered $1$ to $N$ from left to right. For each valid $i$, the $i$-th student has a height $h_{i}$.

Two students $i$ and $j$ can see each other if there are no taller students standing between them. Formally, students $i$ and $j$ ($i < j$) can see each other if for each integer $k$ ($i < k < j$), $h_{k} ≤ h_{i}, h_{j}$.

For each valid $i$, determine the number $c_{i}$ of students that have the same height as student $i$ and can be seen by student $i$.

------  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 $h_{1}, h_{2}, \ldots, h_{N}$.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers $c_{1}, c_{2}, \ldots, c_{N}$.

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

------  Subtasks ------
Subtask #1 (30 points): the sum of $N$ over all test cases does not exceed $10^{3}$

Subtask #2 (70 points): original constraints

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

5

1 2 2 3 2
----- Sample Output 1 ------ 
0 1 1 0 0
----- explanation 1 ------ 
Example case 1: Student $3$ can see students $2$ and $4$, but only student $2$ has the same height (height $2$). On the other hand, student $3$ cannot see student $5$ since student $4$ is taller and therefore blocking the view.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures


Solutions:
tn = int(input())
for _ in range(tn):
	n = int(input())
	l = list(map(int, input().split()))
	lst2 = [None for i in range(n)]
	for i in range(n):
		lst = 0
		if lst2[i] == None:
			for j in range(i + 1, n):
				if l[j] > l[i]:
					break
				elif l[i] == l[j]:
					lst += 1
			for k in range(i, j + 1):
				if l[k] == l[i] and lst2[k] == None:
					lst2[k] = lst
	for i in range(n - 1):
		if lst2[i] != None:
			print(lst2[i], end=' ')
		else:
			print('0', end=' ')
	if lst2[n - 1] != None:
		print(lst2[n - 1])
	else:
		print('0')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	stk = []
	d = {}
	ans = [0] * n
	stk.append(0)
	d[l[0]] = 1
	for i in range(1, n):
		if len(stk) == 0 or l[i] <= l[stk[-1]]:
			stk.append(i)
			d[l[i]] = d.get(l[i], 0) + 1
		else:
			f = set()
			while len(stk) and l[stk[-1]] < l[i]:
				j = stk.pop()
				f.add(l[j])
				ans[j] = d[l[j]] - 1
			for k in f:
				d[k] = 0
			stk.append(i)
			d[l[i]] = d.get(l[i], 0) + 1
	while len(stk):
		j = stk.pop()
		ans[j] = d[l[j]] - 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = [0] * n
	stack = []
	d = {}
	for i in range(n):
		val = None
		while len(stack) > 0 and arr[stack[-1]] < arr[i]:
			ind = stack.pop()
			if val is None or arr[ind] != val:
				if val is not None:
					d[val] = 0
				val = arr[ind]
			ans[ind] = d[arr[ind]] - 1
		if val is not None:
			d[val] = 0
		if d.get(arr[i]) is None:
			d[arr[i]] = 0
		d[arr[i]] += 1
		stack.append(i)
	while len(stack) > 0:
		ind = stack.pop()
		ans[ind] = d[arr[ind]] - 1
	print(*ans)


from sys import stdin, stdout
input = stdin.readline

def func(arr, n):
	stack = list()
	d = dict.fromkeys(arr, 0)
	cnt = [0 for _ in range(n)]
	for i in range(n):
		num = arr[i]
		while stack and stack[-1] < num:
			temp = stack.pop()
			d[temp] = 0
		if stack and stack[-1] == num:
			d[num] += 1
			cnt[i] = d[num]
		stack.append(num)
	return cnt
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	cnt1 = func(arr, n)
	cnt2 = func(arr[::-1], n)
	cnt2 = cnt2[::-1]
	ans = [cnt1[i] + cnt2[i] for i in range(n)]
	print(*ans)


t = int(input())
while t > 0:
	a = int(input())
	arr = [int(i) for i in input().split()]
	ans = [0] * a
	for i in range(a - 1):
		for j in range(i + 1, a):
			if arr[i] < arr[j]:
				break
			if arr[i] == arr[j]:
				ans[i] += 1
				ans[j] += 1
	print(*ans)
	t -= 1


t = int(input())
for _ in range(t):
	N = int(input())
	arr = list(map(int, input().split()))
	ans = [0 for _ in range(len(arr))]
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			if arr[i] == arr[j]:
				ans[i] += 1
				ans[j] += 1
			elif arr[j] > arr[i]:
				break
	print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	c = [0] * n
	for j in range(n):
		for k in range(j + 1, n):
			if h[k] == h[j]:
				c[j] += 1
				c[k] += 1
			elif h[k] > h[j]:
				break
	print(*c)


try:

	def solve(H, N, i):
		count = 0
		X = int(H[i])
		j = int(i) + 1
		i -= 1
		while i >= 0:
			if H[i] > X:
				break
			elif H[i] == X:
				count += 1
			i -= 1
		while j < N:
			if H[j] > X:
				break
			if H[j] == X:
				count += 1
			j += 1
		return count
	for t in range(int(input())):
		N = int(input())
		H = list(map(int, input().split()))
		C = []
		for i in range(N):
			C.append(solve(H, N, i))
		for element in C:
			print(element, end=' ')
		print('')
except:
	pass


case = int(input())
for t in range(case):
	n = int(input())
	h = [int(y) for y in input().split()]
	s = [0] * n
	for i in range(n - 1):
		for j in range(i + 1, n):
			if h[i] < h[j]:
				break
			if h[i] == h[j]:
				s[i] += 1
				s[j] += 1
	print(*s)


def height(arr):
	st = [[float('inf'), 0]]
	ans = []
	for i in arr:
		while st[-1][0] < i:
			st.pop()
		if st[-1][0] != i:
			st.append([i, 0])
		ans.append(st[-1][1])
		st[-1][1] += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()][:n]
	answ = [0] * n
	ans1 = height(a)
	ans2 = height(a[::-1])[::-1]
	for i in range(n):
		answ[i] = ans1[i] + ans2[i]
	print(*answ)


import sys

def sorts(val):
	return val[0]

def gets():
	return list(map(int, sys.stdin.readline().strip().split()))
t = int(input())
for j in range(t):
	a = int(input())
	b = gets()
	c = []
	r = []
	c.append([0, b[0], [0]])
	for k in range(1, len(b)):
		g = 0
		while len(c) > 0 and b[k] >= c[-1][1]:
			if b[k] == c[-1][1]:
				c[-1][2][0] += 1
				g += 1
				break
			else:
				d = c[-1][1]
				r.append((c[-1][0], c[-1][2][0]))
				c.pop()
		if len(c) > 0 and b[k] == c[-1][1]:
			c.append([k, b[k], c[-1][2]])
		else:
			c.append([k, b[k], [g]])
	while len(c) > 0:
		r.append((c[-1][0], c[-1][2][0]))
		c.pop()
	r.sort(key=sorts)
	for l in r:
		print(l[1], end=' ')


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	lst = list(map(int, input().split()))
	new = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if lst[i] == lst[j]:
				new[i] += 1
				new[j] += 1
			elif lst[i] < lst[j]:
				break
	print(*new)


t = int(input())
for x in range(t):
	n = int(input())
	l = [int(y) for y in input().split()]
	tl = [0] * n
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[i] < l[j]:
				break
			if l[i] == l[j]:
				tl[i] += 1
				tl[j] += 1
	print(*tl)


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	s = [0] * x
	for i in range(len(l) - 1):
		for j in range(i + 1, len(l)):
			if l[i] < l[j]:
				break
			elif l[i] == l[j]:
				s[i] += 1
				s[j] += 1
	print(*s)


from sys import stdin
input = stdin.readline

def answer():
	s = []
	ni = [-1] * n
	for i in range(n - 1, -1, -1):
		while len(s) and a[i] >= a[s[-1]]:
			ni[s[-1]] = i
			s.pop()
		s.append(i)
	vis = [False] * (n + 1)
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		if vis[i]:
			continue
		vis[i] = True
		ind = ni[i]
		value = 0
		while ind != -1 and a[ind] == a[i]:
			value += 1
			ind = ni[ind]
		ind = ni[i]
		ans[i] = value
		while ind != -1 and a[ind] == a[i]:
			ans[ind] = value
			vis[ind] = True
			ind = ni[ind]
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(*answer())


num = int(input())
while num > 0:
	a = int(input())
	l = [int(x) for x in input().split()]
	numl = [0] * a
	for i in range(a - 1):
		for j in range(i + 1, a):
			if l[i] < l[j]:
				break
			if l[i] == l[j]:
				numl[i] += 1
				numl[j] += 1
	print(*numl)
	num -= 1


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, input().split()))
	a = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if l[i] == l[j]:
				a[i] += 1
				a[j] += 1
			elif l[i] < l[j]:
				break
	print(*a)


t = int(input())
for i in range(t):
	N = int(input())
	L = list(map(int, input().split()))
	ans = [0] * N
	for i in range(N - 1):
		a = L[i]
		for j in range(i + 1, N):
			if a < L[j]:
				break
			elif a == L[j]:
				ans[i] += 1
				ans[j] += 1
	print(*ans)


for tc in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	op = [0] * len(ls)
	res = [0] * len(ls)
	for x in range(len(ls)):
		if op[x] == 0:
			mx = ls[x]
			se = set()
			cnt = 0
			for y in range(x + 1, len(ls)):
				if ls[y] <= mx:
					if ls[y] == mx:
						cnt += 1
						se.add(y)
						se.add(x)
					else:
						pass
				else:
					break
			if len(se) > 0:
				for dum in se:
					op[dum] = -1
					res[dum] = cnt
	for x in res:
		print(x, end=' ')
	print()


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	temp = [0] * n
	for i in range(len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i] < arr[j]:
				break
			if arr[i] == arr[j]:
				temp[i] += 1
				temp[j] += 1
	print(*temp)
	t -= 1


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	arr = [int(x) for x in input().split(' ')]
	arr1 = [0] * N
	stack = [0]
	aux = []
	for i in range(1, N):
		while len(stack) > 0 and arr[i] > arr[stack[-1]]:
			stack.pop()
		while len(stack) > 0 and arr[i] == arr[stack[-1]]:
			elem = stack.pop()
			aux.append(elem)
			arr1[elem] += 1
			arr1[i] += 1
		while len(aux) > 0:
			stack.append(aux.pop())
		stack.append(i)
		i += 1
	print(*arr1)


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	arr = [int(x) for x in input().split(' ')]
	arr1 = [0] * N
	stack = [(arr[0], 0)]
	dict1 = {arr[0]: [0]}
	i = 1
	while i < N:
		while len(stack) > 0 and arr[i] > stack[-1][0]:
			elem = stack.pop()
			if elem[0] in dict1:
				elemCount = len(dict1[elem[0]])
				for index in dict1[elem[0]]:
					arr1[index] = elemCount - 1
				del dict1[elem[0]]
		stack.append((arr[i], i))
		if arr[i] not in dict1:
			dict1[arr[i]] = [i]
		else:
			dict1[arr[i]].append(i)
		i += 1
	while len(stack) > 0:
		elem = stack.pop()
		if elem[0] in dict1:
			elemCount = len(dict1[elem[0]])
			for index in dict1[elem[0]]:
				arr1[index] = elemCount - 1
			del dict1[elem[0]]
	print(*arr1)


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	ans = [0] * N
	for i in range(N - 1):
		curr = L[i]
		for j in range(i + 1, N):
			if curr < L[j]:
				break
			elif curr == L[j]:
				ans[i] += 1
				ans[j] += 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l1 = [0] * n
	for i in range(0, n):
		a = l[i]
		for j in range(i + 1, n):
			if a == l[j]:
				l1[i] += 1
				l1[j] += 1
			if a < l[j]:
				break
	for i in l1:
		print(i, end=' ')
	print('')


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if a[j] > a[i]:
				break
			elif a[i] == a[j]:
				b[i] += 1
				b[j] += 1
	print(*b, sep=' ')


T = int(input())
for l in range(T):
	N = int(input())
	h = list(map(int, input().split()))
	b = [0] * N
	for i in range(N):
		if b[i] == 0:
			s = []
			s.append(i)
			for j in range(i + 1, N):
				if h[j] > h[i]:
					break
				if h[j] == h[i]:
					s.append(j)
			for k in s:
				b[k] = len(s) - 1
	for k in b:
		print(k, end=' ')


tcs = int(input())

def sol(a):
	st = [[float('inf'), 0]]
	ans = []
	for i in a:
		while st[-1][0] < i:
			st.pop()
		if st[-1][0] != i:
			st.append([i, 0])
		ans.append(st[-1][1])
		st[-1][1] += 1
	return ans
for _ in range(tcs):
	n = int(input())
	h = list(map(int, input().split()))
	ans1 = sol(h)
	ans2 = sol(h[::-1])[::-1]
	for i in range(n):
		ans1[i] += ans2[i]
	print(*ans1)


tcs = int(input())

def sol(a):
	st = [[10 ** 10, 0]]
	ans = []
	for i in range(int(len(a))):
		try:
			while st[-1][0] < a[i]:
				st.pop()
			if st[-1][0] != a[i]:
				st.append([a[i], 0])
			ans.append(st[-1][1])
			st[-1][1] += 1
		except:
			pass
	return ans
for _ in range(tcs):
	n = int(input())
	h = list(map(int, input().split()))
	ans1 = sol(h)
	ans2 = sol(h[::-1])[::-1]
	for i in range(n):
		ans1[i] += ans2[i]
	print(*ans1)


T = int(input())
for _ in range(T):
	N = int(input())
	Nh = list(map(int, input().split()))
	ans = [0] * N
	for i in range(N):
		for j in range(i + 1, N):
			if Nh[i] < Nh[j]:
				break
			elif Nh[i] == Nh[j]:
				ans[i] += 1
				ans[j] += 1
	print(*ans)


for _ in range(int(input())):
	N = int(input())
	h = list(map(int, input().split()))[:N]
	zero = [0] * N
	for i in range(N):
		if zero[i] == 0:
			s = []
			s.append(i)
			for j in range(i + 1, N):
				if h[j] > h[i]:
					break
				if h[j] == h[i]:
					s.append(j)
			for m in s:
				zero[m] = len(s) - 1
	print(*zero)


tc = int(input())
for _ in range(tc):
	n = int(input())
	l = [int(x) for x in input().split()]
	res = [0] * n
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[j] > l[i]:
				break
			if l[i] == l[j]:
				res[i] += 1
				res[j] += 1
	for i in res:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	for x in range(n - 1):
		for j in range(x + 1, n):
			if arr[j] > arr[x]:
				break
			elif arr[j] == arr[x]:
				ans[x] += 1
				ans[j] += 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	c = [0] * len(h)
	for i in range(len(h)):
		for j in range(i + 1, len(h)):
			if h[i] == h[j]:
				c[j] += 1
				c[i] += 1
			elif h[j] > h[i]:
				break
	print(*c)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = [0] * len(l)
	for j in range(len(l)):
		for k in range(j + 1, len(l)):
			if l[j] == l[k]:
				s[k] += 1
				s[j] += 1
			elif l[k] > l[j]:
				break
	print(*s, sep=' ')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if i in d:
			continue
		x = l[i]
		s = set()
		s.add(i)
		for j in range(i + 1, n):
			y = l[j]
			if y > x:
				break
			if y == x:
				s.add(j)
		for k in s:
			d[k] = len(s) - 1
	ans = [0] * n
	for i in d:
		ans[i] = d[i]
	print(*ans)


def prog_name():
	n = int(input())
	l = list(map(int, input().split()))
	final = []
	for x in range(len(l)):
		c = 0
		for y in range(x + 1, len(l)):
			if l[y] > l[x]:
				break
			elif l[y] == l[x]:
				c += 1
		for z in range(x - 1, -1, -1):
			if l[z] > l[x]:
				break
			elif l[z] == l[x]:
				c += 1
		final.append(str(c))
	print(' '.join(final))
t = int(input())
for unique in range(t):
	prog_name()


import sys, math, itertools, random, bisect
from collections import defaultdict
inf = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = get_array()
	a.append(inf)
	ans = [0] * n
	st = [0]
	for i in range(1, n + 1):
		store = defaultdict(list)
		while st and a[st[-1]] < a[i]:
			pos = st.pop()
			store[a[pos]].append(pos)
		st.append(i)
		for key in store:
			ct = len(store[key]) - 1
			for x in store[key]:
				ans[x] = ct
	print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if a[j] > a[i]:
				break
			elif a[j] == a[i]:
				b[j] += 1
				b[i] += 1
	print(*b)


import math
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	stack = [[math.inf, 0]]
	res = []
	for i in range(n):
		while len(stack) != 0 and stack[-1][0] < l[i]:
			stack.pop(-1)
		if stack[-1][0] != l[i]:
			stack.append([l[i], 0])
		res.append(stack[-1][1])
		stack[-1][1] += 1
	l = l[::-1]
	stack = [[math.inf, 0]]
	res1 = []
	for i in range(n):
		while len(stack) != 0 and stack[-1][0] < l[i]:
			stack.pop(-1)
		if stack[-1][0] != l[i]:
			stack.append([l[i], 0])
		res1.append(stack[-1][1])
		stack[-1][1] += 1
	res1 = res1[::-1]
	for i in range(n):
		res[i] = res[i] + res1[i]
	print(*res)
	t -= 1


try:
	t = int(input())
	for i in range(0, t):
		n = int(input())
		a = list(map(int, input().split(' ')))
		b = [0] * n
		for i in range(0, len(b)):
			if b[i] == 0:
				s = []
				s.append(i)
				for j in range(i + 1, n):
					if a[j] > a[i]:
						break
					if a[j] == a[i]:
						s.append(j)
				for v in s:
					b[v] = len(s) - 1
		print(*b)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	(stack, aux) = ([0], [])
	answer = [0] * n
	for i in range(1, n):
		while len(stack) > 0 and array[i] > array[stack[-1]]:
			stack.pop()
		while len(stack) > 0 and array[i] == array[stack[-1]]:
			x = stack.pop()
			aux.append(x)
			answer[x] += 1
			answer[i] += 1
		while len(aux) > 0:
			stack.append(aux.pop())
		stack.append(i)
	for i in answer:
		print(i, end=' ')
	print('')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	op = [0] * len(arr)
	for i in range(len(arr) - 1):
		curr = arr[i]
		for j in range(i + 1, len(arr)):
			if curr == arr[j]:
				op[i] += 1
				op[j] += 1
			elif curr < arr[j]:
				break
	for el in op:
		print(str(el), end=' ')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n - 1):
		curr = a[i]
		for j in range(i + 1, n):
			if a[i] == a[j]:
				if curr <= a[i]:
					ans[i] += 1
					ans[j] += 1
			elif curr < a[j]:
				break
	ans = [str(ans[i]) for i in range(len(ans))]
	print(' '.join(ans))


T = int(input())
for t in range(0, T):
	N = int(input())
	ip = input()
	temp = ip.split()
	arr = []
	for i in range(len(temp)):
		ele = int(temp[i])
		arr.append(ele)
	op = []
	for i in range(0, len(arr)):
		op.append(0)
	for i in range(0, len(op) - 1):
		curr = arr[i]
		for j in range(i + 1, len(op)):
			if arr[i] == arr[j]:
				if curr <= arr[i]:
					op[i] += 1
					op[j] += 1
			elif curr < arr[j]:
				break
	string = ''
	for i in range(0, len(op)):
		string = string + str(op[i])
		string = string + ' '
	print(string)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = ([-1 for i in range(n)], [-1 for i in range(n)])
	for i in range(n - 1):
		if l[i] == -1:
			l[i] = 0
			c = 1
			for j in range(i + 1, n):
				if a[i] == a[j]:
					l[j] = c
					c += 1
				elif a[j] > a[i]:
					break
	for i in range(n - 1, 0, -1):
		if r[i] == -1:
			r[i] = 0
			c = 1
			for j in range(i - 1, -1, -1):
				if a[i] == a[j]:
					r[j] = c
					c += 1
				elif a[j] > a[i]:
					break
	for i in range(n):
		print(max(0, l[i] + r[i]), end=' ')
	print()
for _ in range(int(input())):
	solve()


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 4)
t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	left = []
	jump_left = []
	S = []
	for i in range(n):
		while len(S) != 0:
			top = S[-1]
			if ls[top] >= ls[i]:
				jump_left.append(top)
				break
			else:
				S.pop()
		else:
			jump_left.append(-1)
		S.append(i)
	for i in range(n):
		if jump_left[i] == -1 or ls[jump_left[i]] > ls[i]:
			left.append(0)
		else:
			left.append(1 + left[jump_left[i]])
	right = []
	jump_right = []
	S = []
	ls.reverse()
	for i in range(n):
		while len(S) != 0:
			top = S[-1]
			if ls[top] >= ls[i]:
				jump_right.append(top)
				break
			else:
				S.pop()
		else:
			jump_right.append(-1)
		S.append(i)
	for i in range(n):
		if jump_right[i] == -1 or ls[jump_right[i]] > ls[i]:
			right.append(0)
		else:
			right.append(1 + right[jump_right[i]])
	right.reverse()
	for i in range(n):
		print(left[i] + right[i], end=' ')


class Stack:

	def __init__(self):
		self.data = list()

	def top(self):
		return self.data[-1] if self.data else None

	def is_empty(self):
		return not self.data

	def push(self, element):
		self.data.append(element)

	def pop(self):
		return self.data.pop()

def get_next_largest_or_equal(array) -> dict:
	stack = Stack()
	next_largest_element_index = dict()
	for (current_element_index, current_element_value) in enumerate(array):
		current_element = (current_element_value, current_element_index)
		while stack.is_empty() is not True and current_element_value >= stack.top()[0]:
			popped_element = stack.pop()
			next_largest_element_index[popped_element[1]] = current_element_index
		stack.push(current_element)
	return next_largest_element_index

def get_visible_people(array, next_equal_or_greater_indices, direction) -> list:
	_array_length = len(array)
	visible_people = [0 for _ in range(_array_length)]
	_index = _array_length - 1 if direction == 'RIGHT' else 0
	while 0 <= _index < _array_length:
		next_element_index = next_equal_or_greater_indices.get(_index, None)
		if next_element_index is None:
			visible_people[_index] = 0
		elif array[next_element_index] > array[_index]:
			visible_people[_index] = 0
		elif array[next_element_index] == array[_index]:
			visible_people[_index] = visible_people[next_element_index] + 1
		_index = _index - 1 if direction == 'RIGHT' else _index + 1
	return visible_people
T = int(input())
for _ in range(T):
	N = int(input())
	ARRAY = list(map(int, input().split(' ')))
	array_length = len(ARRAY)
	right_element_indices = get_next_largest_or_equal(array=ARRAY)
	right_visible_people = get_visible_people(array=ARRAY, next_equal_or_greater_indices=right_element_indices, direction='RIGHT')
	left_element_indices = get_next_largest_or_equal(array=reversed(ARRAY))
	left_element_indices = {array_length - 1 - i: array_length - 1 - j for (i, j) in left_element_indices.items()}
	left_visible_people = get_visible_people(array=ARRAY, next_equal_or_greater_indices=left_element_indices, direction='LEFT')
	combined = []
	for index in range(array_length):
		combined.append(left_visible_people[index] + right_visible_people[index])
	print(' '.join((str(val) for val in combined)))


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	stack = []
	stack.append([float('inf'), 0])
	left = []
	for e in l:
		while stack[-1][0] < e:
			stack.pop()
		if stack[-1][0] != e:
			stack.append([e, 0])
		left.append(stack[-1][1])
		stack[-1][1] += 1
	l.reverse()
	st = []
	st.append([float('inf'), 0])
	right = []
	for e in l:
		while st[-1][0] < e:
			st.pop()
		if st[-1][0] != e:
			st.append([e, 0])
		right.append(st[-1][1])
		st[-1][1] += 1
	right.reverse()
	for j in range(n):
		print(left[j] + right[j], end=' ')
	print()


t = int(input())
for i in range(0, t):
	n = int(input())
	b = [0] * n
	a = list(map(int, input().split()))
	for j in range(0, n - 1):
		c = a[j]
		for k in range(j + 1, n):
			if a[k] > c:
				break
			if a[k] == c:
				b[j] += 1
				b[k] += 1
	for o in b:
		print(o, end=' ')
	print()


def check(li):
	st = [[float('inf'), 0]]
	ans = []
	for i in li:
		while st[-1][0] < i:
			st.pop()
		if st[-1][0] != i:
			st.append([i, 0])
		ans.append(st[-1][1])
		st[-1][1] += 1
	return ans
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	left = check(arr)
	right = check(arr[::-1])
	right = right[::-1]
	ans = []
	for i in range(n):
		ans.append(left[i] + right[i])
	for i in ans:
		print(i, end=' ')
	print()


def check(n, array):
	for i in range(0, n):
		total = 0
		for j in range(i - 1, -1, -1):
			if array[i] > array[j]:
				pass
			elif array[i] == array[j]:
				total += 1
			else:
				break
		for j in range(i + 1, n):
			if array[i] > array[j]:
				pass
			elif array[i] == array[j]:
				total += 1
			else:
				break
		print(total, end=' ')
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	check(n, arr)
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	h_vec = input().split(' ')
	h_vec = [int(h) for h in h_vec]
	stack = []
	next_equal_left = [0 for _ in range(n)]
	next_equal_right = [0 for _ in range(n)]
	for i in range(n):
		while len(stack) > 0:
			index = stack[-1]
			if h_vec[index] >= h_vec[i]:
				break
			stack.pop()
		if len(stack) > 0:
			next_equal_left[i] = stack[-1]
		else:
			next_equal_left[i] = -1
		stack.append(i)
	stack = []
	for i in range(n - 1, -1, -1):
		while len(stack) > 0:
			index = stack[-1]
			if h_vec[index] >= h_vec[i]:
				break
			stack.pop()
		if len(stack) > 0:
			next_equal_right[i] = stack[-1]
		else:
			next_equal_right[i] = -1
		stack.append(i)
	left_result = [0 for _ in range(n)]
	right_result = [0 for _ in range(n)]
	for i in range(n):
		if next_equal_left[i] == -1 or h_vec[i] != h_vec[next_equal_left[i]]:
			continue
		else:
			left_result[i] = left_result[next_equal_left[i]] + 1
	for i in range(n - 1, -1, -1):
		if next_equal_right[i] == -1 or h_vec[i] != h_vec[next_equal_right[i]]:
			continue
		else:
			right_result[i] = right_result[next_equal_right[i]] + 1
	res = [0 for _ in range(n)]
	for i in range(n):
		res[i] = left_result[i] + right_result[i]
	res = [str(r) for r in res]
	res = ' '.join(res)
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0 for i in range(n)]
	dp[n - 1] = 0
	st = [(a[n - 1], n - 1)]
	for i in range(n - 2, -1, -1):
		while st and a[i] > st[-1][0]:
			st.pop()
		if st:
			if st[-1][0] == a[i]:
				dp[st[-1][1]] += 1
				dp[i] += dp[st[-1][1]]
				st.pop()
		st.append((a[i], i))
	st = [(a[0], 0)]
	for i in range(1, n):
		while st and st[-1][0] < a[i]:
			st.pop()
		if st:
			if st[-1][0] == a[i]:
				dp[i] = dp[st[-1][1]]
		st.append((a[i], i))
	print(*dp)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	left = [0] * n
	stack = []
	for i in range(n):
		while len(stack) > 0 and lis[stack[0]] < lis[i]:
			stack.pop(0)
		if len(stack) == 0 or lis[stack[0]] > lis[i]:
			left[i] = 0
		elif lis[stack[0]] == lis[i]:
			left[i] = left[stack[0]] + 1
			stack.pop(0)
		stack.insert(0, i)
	right = [0] * n
	stack = []
	for i in range(n - 1, -1, -1):
		while len(stack) > 0 and lis[stack[0]] < lis[i]:
			stack.pop(0)
		if len(stack) == 0 or lis[stack[0]] > lis[i]:
			right[i] = 0
		elif lis[stack[0]] == lis[i]:
			right[i] = right[stack[0]] + 1
			stack.pop(0)
		stack.insert(0, i)
	ans = [left[i] + right[i] for i in range(n)]
	print(*ans)


from collections import defaultdict
t = int(input())
for k in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		ans = [0] * n
		stack = []
		k = max(arr) + 1
		visited = defaultdict(int)
		stack.append(arr[0])
		visited[arr[0]] = 1
		for j in range(1, n):
			if arr[j] > stack[-1]:
				while len(stack) != 0 and arr[j] > stack[-1]:
					visited[stack.pop()] = 0
			ans[j] += visited[arr[j]]
			stack.append(arr[j])
			visited[arr[j]] += 1
		stack = []
		stack.append(arr[n - 1])
		visit = defaultdict(int)
		visit[arr[n - 1]] = 1
		for j in range(n - 2, -1, -1):
			if arr[j] > stack[-1]:
				while len(stack) != 0 and arr[j] > stack[-1]:
					visit[stack.pop()] = 0
			ans[j] += visit[arr[j]]
			stack.append(arr[j])
			visit[arr[j]] += 1
		print(*ans)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	c = [0] * n
	for i in range(n):
		if c[i] == 0:
			l = []
			ans = 0
			for j in range(i + 1, n):
				if x[j] > x[i]:
					break
				elif x[j] == x[i]:
					c[i] += 1
					l.append(j)
			for k in range(len(l)):
				c[l[k]] = c[i]
	print(*c)


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