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

There are $N$ athletes (numbered $1$ through $N$) in a line. For each valid $i$, the $i$-th athlete starts at the position $i$ and his speed is $V_{i}$, i.e. for any real number $t ≥ 0$, the position of the $i$-th athlete at the time $t$ is $i + V_{i} \cdot t$.

Unfortunately, one of the athletes is infected with a virus at the time $t = 0$. This virus only spreads from an infected athlete to another whenever their positions are the same at the same time. A newly infected athlete may then infect others as well.

We do not know which athlete is infected initially. However, if we wait long enough, a specific set of athletes (depending on the athlete that was infected initially) will become infected. Your task is to find the size of this set, i.e. the final number of infected people, in the best and worst possible scenario.

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

------  Output ------
For each test case, print a single line containing two space-separated integers ― the smallest and largest final number of infected people.

------  Constraints ------
$1 ≤ T ≤ 10^{4}$
$3 ≤ N ≤ 5$
$0 ≤ V_{i} ≤ 5$ for each valid $i$

------  Subtasks ------
Subtask #1 (1 point): $N = 3$

Subtask #2 (99 points): original constraints

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

3

1 2 3

3

3 2 1

3

0 0 0

3

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

3 3

1 1

1 2
----- explanation 1 ------ 
Example case 1: No two athletes will ever have the same position, so the virus cannot spread.

Example case 2: It does not matter who is initially infected, the first athlete would always spread it to everyone.

Example case 3: The athletes are not moving, so the virus cannot spread.

Example case 4: The best possible scenario is when the initially infected athlete is the first one, since he cannot infect anyone else. In the worst possible scenario, eventually, the second and third athletes are infected.

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(b, w) = (n, 1)
	for i in range(n):
		a = [0] * n
		a[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				a[j] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				a[j] = 1
		for j in range(i):
			if a[j] == 1:
				for z in range(i, n):
					if l[z] < l[j]:
						a[z] = 1
		for j in range(i + 1, n):
			if a[j] == 1:
				for y in range(i):
					if l[j] < l[y]:
						a[y] = 1
		f = a.count(1)
		w = max(f, w)
		b = min(f, b)
	print(b, w)


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	l = li()
	b = n
	w = 1
	for i in range(n):
		a = [0] * n
		a[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				a[j] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				a[j] = 1
		for j in range(i):
			if a[j] == 1:
				for k in range(i, n):
					if l[k] < l[j]:
						a[k] = 1
		for j in range(i + 1, n):
			if a[j] == 1:
				for y in range(i):
					if l[j] < l[y]:
						a[y] = 1
		f = a.count(1)
		w = max(f, w)
		b = min(f, b)
	print(b, w)


for _ in range(int(input())):
	num = int(input())
	l = [int(x) for x in input().split()]
	(best, worst) = (num, 1)
	for i in range(num):
		temp = [0] * num
		temp[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				temp[j] = 1
		for j in range(i + 1, num):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, num):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, num):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		cnt = temp.count(1)
		worst = max(cnt, worst)
		best = min(cnt, best)
	print(best, worst)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	mp = defaultdict(list)
	best = n
	worst = 0
	for i in range(n):
		for j in range(i + 1, n):
			if v[i] > v[j]:
				t = (j - i) / (v[i] - v[j])
				x = i + v[i] * t
				mp[t, x].append(i)
				mp[t, x].append(j)
	for i in range(n):
		infected = [False] * n
		infected[i] = True
		for p in sorted(mp.keys(), key=lambda x: x[0]):
			spread = False
			for el in mp[p]:
				spread |= infected[el]
			if spread:
				for el in mp[p]:
					infected[el] = True
		count = 0
		for el in infected:
			count += el
		best = min(best, count)
		worst = max(worst, count)
	print(best, worst)


for _ in range(int(input())):
	n = int(input())
	vloc = list(map(int, input().strip().split()))
	covid = []
	for i in range(n):
		for j in range(i):
			v = vloc[i] - vloc[j]
			if v < 0:
				t = (j - i) / v
				covid.append((t, j, i))
	covid.sort()
	maxv = -1
	minv = n + 1
	for i in range(n):
		infected = {i: 1}
		for (t, a, b) in covid:
			if a in infected:
				infected[b] = 1
			if b in infected:
				infected[a] = 1
		maxv = max(maxv, len(infected))
		minv = min(minv, len(infected))
	print(minv, maxv)


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	velocity = list(map(int, input().split()))
	d = defaultdict(set)
	for i in range(N):
		for j in range(i + 1, N):
			if j > i and velocity[i] > velocity[j]:
				x = velocity[i] - velocity[j]
				y = j - i
				t = round(y / x, 2)
				x = i + velocity[i] * t
				d[t, x].add(i)
				d[t, x].add(j)
	mini = 9999999999999
	maxi = -1
	for i in range(N):
		infected = [False] * N
		infected[i] = True
		for key in sorted(d.keys()):
			spread = False
			for val in d[key]:
				spread |= infected[val]
			if spread:
				for val in d[key]:
					infected[val] = True
		Tval = 0
		for value in infected:
			if value:
				Tval += 1
		maxi = max(Tval, maxi)
		mini = min(Tval, mini)
	print(mini, maxi, end=' ')
	print()


def getAllPositive(matrix, inf, n, p, t):
	for i in range(n):
		if matrix[p][i] > t:
			inf.add(i)
			getAllPositive(matrix, inf, n, i, matrix[p][i])
for _ in range(int(input())):
	n = int(input())
	S = list(map(int, input().split()))
	T = []
	for i in range(n):
		flag = [0] * n
		for j in range(n):
			if i == j or S[i] == S[j]:
				flag[j] = -1
			else:
				time = (i - j) / (S[j] - S[i])
				if time < 0:
					flag[j] = -1
				else:
					flag[j] = time
		T.append(flag)
	positive = []
	for i in range(n):
		inf = set()
		inf.add(i)
		getAllPositive(T, inf, n, i, 0)
		positive.append(len(inf))
	print(min(positive), max(positive))


import sys

def ammala(i, t0, malati):
	for j in range(n):
		if j not in malati:
			if vel[i] != vel[j]:
				t = (j - i) / (vel[i] - vel[j])
				if t >= t0:
					malati.append(j)
					malati = ammala(j, t, malati)
	return malati
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	vel = []
	vel[:] = map(int, input().strip().split())
	massimo = 0
	minimo = 10
	for i in range(n):
		malati = ammala(i, 0, [i])
		massimo = max(massimo, len(malati))
		minimo = min(minimo, len(malati))
	print(minimo, massimo)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().strip().split()))
	ans = []
	for i in range(n):
		speed = list1[i]
		max_speed = -1000
		min_speed = 1000
		count = 1
		for j in range(0, i):
			if list1[j] > speed:
				count += 1
				if list1[j] > max_speed:
					max_speed = list1[j]
		for j in range(i + 1, n):
			if list1[j] < speed:
				count += 1
				if list1[j] < min_speed:
					min_speed = list1[j]
		for j in range(0, i):
			if list1[j] <= speed and list1[j] > min_speed:
				count += 1
		for j in range(i + 1, n):
			if list1[j] >= speed and list1[j] < max_speed:
				count += 1
		ans.append(count)
	print(min(ans), max(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(best, worst) = (n, 1)
	for i in range(n):
		temp = [0] * n
		temp[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				temp[j] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, n):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, n):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		c = temp.count(1)
		worst = max(c, worst)
		best = min(c, best)
	print(best, worst)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	max1 = 1
	min1 = n
	for i in range(n):
		temp = [0] * n
		temp[i] = 1
		for k in range(i):
			if l[k] > l[i]:
				temp[k] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, n):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, n):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		max1 = max(max1, temp.count(1))
		min1 = min(min1, temp.count(1))
	print(min1, max1)


from collections import defaultdict

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	mi = 1000000000.0
	ma = 1
	temp = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				t = (j - i) / (arr[i] - arr[j])
				x = arr[i] * t + i
				temp[t, x].append(i)
				temp[t, x].append(j)
	for i in range(n):
		caught = [False] * n
		caught[i] = True
		for j in sorted(temp.keys(), key=lambda x: x[0]):
			flag = 0
			for k in temp[j]:
				if caught[k] == True:
					flag = 1
					break
			if flag == 1:
				for k in temp[j]:
					caught[k] = True
		count = 0
		for j in caught:
			if j == True:
				count += 1
		mi = min(mi, count)
		ma = max(ma, count)
	print(mi, ma)
try:
	for _ in range(int(input())):
		solve()
except:
	pass


import collections
tc = int(input())
while tc > 0:
	tc = tc - 1
	n = int(input())
	arr = []
	max = 1
	min = n
	temp = 1
	arr = [int(i) for i in input().split()]
	dict = collections.defaultdict(list)
	for i in range(0, n):
		for j in range(0, n):
			if arr[i] > arr[j] and j > i:
				t = (j - i) / (arr[i] - arr[j])
				x = i + arr[i] * t
				dict[t, x].append(i)
				dict[t, x].append(j)
	for i in range(n):
		infected = [False for j in range(n)]
		infected[i] = True
		for p in sorted(dict.keys(), key=lambda x: x[0]):
			spread = False
			for el in dict[p]:
				if infected[el] == True:
					spread = True
			if spread == True:
				for el in dict[p]:
					infected[el] = True
		count = 0
		for i in range(n):
			if infected[i] == True:
				count += 1
		if count > max:
			max = count
		if count < min:
			min = count
	print(min, max)


from array import *
tc = int(input())
for _ in range(tc):
	n = int(input())
	v = list(map(int, input().split()))[:n]
	pos_time = [[False] * n for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			if v[i] > v[j]:
				t = (j - i) / (v[i] - v[j])
				x = (i + v[i] * t, t)
				pos_time[i][j] = x
	pos_time_dict = dict()
	dict_keys = []
	for i in range(n):
		for j in range(n):
			if pos_time[i][j] != False:
				pos_time_dict[pos_time[i][j]] = set()
				dict_keys.append(pos_time[i][j])
	for i in range(n):
		for j in range(n):
			if pos_time[i][j] != False:
				pos_time_dict[pos_time[i][j]].add(i)
				pos_time_dict[pos_time[i][j]].add(j)
	dict_keys.sort(key=lambda tup: tup[1])
	max_affected = -1
	min_affected = n + 1
	for i in range(n):
		affected = [False for _ in range(n)]
		affected[i] = True
		for k in dict_keys:
			for m in range(len(affected)):
				if m in pos_time_dict[k] and affected[m] == True:
					for p in pos_time_dict[k]:
						affected[p] = True
		aff = affected.count(True)
		if aff > max_affected:
			max_affected = aff
		if aff < min_affected:
			min_affected = aff
	print(min_affected, max_affected)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	for i in range(n):
		speed = l[i]
		tans = set()
		tans.add(i)
		mx = speed
		mn = speed
		for j in range(i):
			if l[j] > speed:
				tans.add(j)
			mx = max(mx, l[j])
		for j in range(i + 1, n):
			if l[j] < mx:
				tans.add(j)
			mn = min(mn, l[j])
		for j in range(i):
			if l[j] > mn:
				tans.add(j)
		ans.append(len(tans))
	print(min(ans), max(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	upi = [l[0]] * n
	if upi == l:
		print('1 1')
		continue
	dp = []
	for i in range(n):
		j = [0] * (n + 1)
		dp.append(j)
	dp[0][0] = 1
	for i in range(n):
		afc = []
		besa = []
		for j in range(0, n):
			if i != j and l[i] < l[j]:
				if i > j:
					if j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i][j - 1] + 1
				elif j != 0:
					dp[i][j] = dp[i][j - 1]
			elif i != j and l[i] > l[j]:
				if i < j:
					if j == 0:
						dp[i][j] = 1
					else:
						dp[i][j] = dp[i][j - 1] + 1
				elif j != 0:
					dp[i][j] = dp[i][j - 1]
			elif i == j:
				if j == 0 and i == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i][j - 1] + 1
			else:
				dp[i][j] = dp[i][j - 1]
		for uio in range(0, n):
			if uio != i:
				if uio != 0 and dp[i][uio] == dp[i][uio - 1] or (uio == 0 and dp[i][uio] == 0):
					if l[uio] <= l[i] and uio < i:
						for tio in range(i + 1, n):
							if l[tio] < l[uio] and l[uio] <= l[i]:
								dp[i][n] += 1
								break
					if uio > i and l[uio] >= l[i]:
						for tio in range(0, i):
							if l[tio] > l[uio] and l[uio] >= l[i]:
								dp[i][n] += 1
								break
	k = []
	for _ in range(n):
		k.append(dp[_][n - 1] + dp[_][n])
	print(min(k), max(k))


def rec(mat, s, p, n, t):
	for i in range(n):
		if mat[i][p] > t:
			s.add(i)
			rec(mat, s, i, n, mat[i][p])

def covid(l):
	mat = []
	for i in range(len(l)):
		temp = []
		for j in range(len(l)):
			if l[i] == l[j]:
				temp.append(-1)
			else:
				t = (i - j) / (l[j] - l[i])
				if t <= 0:
					temp.append(-1)
				else:
					temp.append(t)
		mat.append(temp)
	s = set()
	v = []
	for i in range(len(l)):
		s.add(i)
		rec(mat, s, i, len(l), 0)
		v.append(len(s))
		s.clear()
	print(min(v), max(v))
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	covid(l)


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	(best, worst) = (n, 1)
	for i in range(n):
		temp = [0] * n
		temp[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				temp[j] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, n):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, n):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		c = temp.count(1)
		worst = max(c, worst)
		best = min(c, best)
	print(best, worst)
	t -= 1


for i in range(int(input())):
	item = int(input())
	size = []
	st = list(map(int, input().split()))
	for j in range(len(st)):
		flip = 1
		fmn = st[j]
		fmx = st[j]
		for k in range(j + 1, item):
			if st[j] > st[k]:
				if fmn > st[k]:
					fmn = st[k]
		for a in range(0, j):
			if st[a] > st[j]:
				if fmx < st[a]:
					fmx = st[a]
			if st[a] > fmn:
				flip = flip + 1
		for x in range(j + 1, item):
			if st[x] < fmx:
				flip = flip + 1
		size.append(flip)
	print(min(size), max(size))


for i in range(int(input())):
	item = int(input())
	size = []
	st = list(map(int, input().split()))
	for j in range(len(st)):
		con = 1
		minn = st[j]
		maxx = st[j]
		for k in range(j + 1, item):
			if st[j] > st[k]:
				if minn > st[k]:
					minn = st[k]
		for a in range(0, j):
			if st[a] > st[j]:
				if maxx < st[a]:
					maxx = st[a]
			if st[a] > minn:
				con = con + 1
		for x in range(j + 1, item):
			if st[x] < maxx:
				con = con + 1
		size.append(con)
	print(min(size), max(size))


for i in range(int(input())):
	num = int(input())
	N = []
	li = list(map(int, input().split()))
	for j in range(len(li)):
		con = 1
		minn = li[j]
		maxx = li[j]
		for k in range(j + 1, num):
			if li[j] > li[k]:
				if minn > li[k]:
					minn = li[k]
		for a in range(0, j):
			if li[a] > li[j]:
				if maxx < li[a]:
					maxx = li[a]
			if li[a] > minn:
				con = con + 1
		for x in range(j + 1, num):
			if li[x] < maxx:
				con = con + 1
		N.append(con)
	print(min(N), max(N))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	d = {}
	best = n
	worst = 0
	for i in range(n):
		for j in range(i + 1, n):
			if lst[i] > lst[j]:
				t = (j - i) / (lst[i] - lst[j])
				x = i + lst[i] * t
				if (t, x) in d:
					d[t, x].append(i)
					d[t, x].append(j)
				else:
					d[t, x] = [i, j]
	for i in range(n):
		arr = [0] * n
		arr[i] = 1
		for j in sorted(d.keys()):
			flag = 0
			for k in d[j]:
				if arr[k] == 1:
					flag = 1
			if flag:
				for k in d[j]:
					arr[k] = 1
		ctr = 0
		for k in range(n):
			if arr[k] == 1:
				ctr += 1
		best = min(best, ctr)
		worst = max(worst, ctr)
	print(best, worst)


def do_infect(a, b, x, y):
	k = b - a
	if k != 0:
		t = (x - y) / k
		if t > 0:
			return True
		else:
			return False
	else:
		return False

def met_time(a, b, x, y):
	k = b - a
	if k != 0:
		t = (x - y) / k
		if t > 0:
			return t
		else:
			return 0
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = []
	for i in range(n):
		x = [0] * n
		x[i] = 1
		time = [0] * n
		for j in range(n):
			if i == j:
				continue
			elif do_infect(a[i], a[j], i + 1, j + 1):
				x[j] = 1
				time[j] = met_time(a[i], a[j], i + 1, j + 1)
		for j in range(n):
			if i == j:
				continue
			elif x[j] == 1:
				for l in range(n):
					if l == j or l == i:
						continue
					elif do_infect(a[j], a[l], j + 1, l + 1) and met_time(a[j], a[l], j + 1, l + 1) >= time[j]:
						x[l] = 1
						time[l] = met_time(a[j], a[l], j + 1, l + 1)
		ans.append(x.count(1))
	print(min(ans), max(ans))


def rec(g, s, i, n, t):
	for k in range(0, n):
		if g[i][k] > t:
			s.add(k)
			rec(g, s, k, n, g[i][k])
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	g = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			if i == j:
				g[i][j] = -1
			elif arr[i] == arr[j]:
				g[i][j] = -1
			else:
				d1 = (i - j) / (arr[j] - arr[i])
				if d1 <= 0:
					g[i][j] = -1
				else:
					g[i][j] = d1
	s = set()
	v = []
	for i in range(n):
		s.add(i)
		rec(g, s, i, n, 0)
		v.append(len(s))
		s.clear()
	print(min(v), max(v))


t = int(input())
for _ in range(t):
	n = int(input())
	vels = [int(i) for i in input().split()]
	timeCount = {}
	for i in range(n):
		for j in range(i + 1, n):
			if vels[i] > vels[j]:
				equalTime = (j - i) / (vels[i] - vels[j])
				equalDist = i + vels[i] * equalTime
				try:
					timeCount[equalTime, equalDist].update([i, j])
				except:
					timeCount[equalTime, equalDist] = set([i, j])
	minVal = None
	maxVal = None
	timeKeys = sorted(timeCount.keys())
	for i in range(n):
		infected = set([i])
		for j in timeKeys:
			if len(infected.intersection(timeCount[j])) != 0:
				infected.update(timeCount[j])
		if minVal == None or len(infected) < minVal:
			minVal = len(infected)
		if maxVal == None or len(infected) > maxVal:
			maxVal = len(infected)
	print(minVal, maxVal)


for _ in range(int(input())):
	n = int(input())
	mx = 0
	mn = n + 1
	v = list(map(int, input().split()))
	for i in range(n):
		tmp = [0] * n
		tmp[i] = 1
		for j in range(i):
			if v[j] > v[i]:
				tmp[j] = 1
		for j in range(i + 1, n):
			if v[j] < v[i]:
				tmp[j] = 1
		for j in range(i):
			if tmp[j]:
				for k in range(i, n):
					if v[j] > v[k]:
						tmp[k] = 1
		for j in range(i + 1, n):
			if tmp[j]:
				for k in range(i):
					if v[k] > v[j]:
						tmp[k] = 1
		cnt = tmp.count(1)
		mx = max(cnt, mx)
		mn = min(cnt, mn)
	print(mn, mx)


def prog():
	v = list(map(int, input().split()))
	affected = []
	for i in range(0, n):
		nmore = 0
		nless = 0
		maxv = v[i]
		minv = v[i]
		for j in range(0, i):
			if v[j] > v[i]:
				nmore += 1
				if v[j] > maxv:
					maxv = v[j]
		for k in range(i + 1, n):
			if v[k] < maxv:
				nless += 1
			if v[k] < minv:
				minv = v[k]
		for l in range(0, i):
			if v[l] > minv and v[l] <= v[i]:
				nmore += 1
		total = nmore + nless + 1
		affected.append(total)
	print(min(affected), max(affected))
test = int(input())
for _ in range(0, test):
	n = int(input())
	prog()


from collections import defaultdict
T = int(input())
for _ in range(T):
	N = int(input())
	V = list(map(int, input().split()))
	min_infections = float('inf')
	max_infections = 1
	infections = defaultdict(list)
	for i in range(N - 1):
		for j in range(i + 1, N):
			if V[i] > V[j]:
				t = (j - i) * 60 / (V[i] - V[j])
				x = i * 60 + V[i] * t
				infections[t, x].append(i)
				infections[t, x].append(j)
	for i in range(N):
		infected = [False] * N
		infected[i] = True
		for key in sorted(infections.keys()):
			if any(map(lambda i: infected[i], infections[key])):
				for athlete in infections[key]:
					infected[athlete] = True
		total_infections = sum(infected)
		min_infections = min(min_infections, total_infections)
		max_infections = max(max_infections, total_infections)
	print(min_infections, max_infections)


def solve(i, v, n, v1):
	ans = 1
	inf = 1
	for j in range(n):
		if v[j] == v[i] or j == i:
			continue
		t = float(i - j) / float(v[j] - v[i])
		if t >= v2[i] and v1[j] == 0:
			inf += 1
			v1[j] = 1
			v2[j] = t
			ans += solve(j, v, n, v1)
	return ans

def iList(l, n):
	for i in range(n + 1):
		l[i] = 0
	for j in range(12):
		pass
for _ in range(int(input())):
	cmin = 1000000000
	cmax = -1000000000
	n = int(input())
	v = [int(x) for x in input().split()]
	v1 = []
	v2 = []
	v1 = [0] * (n + 1)
	v2 = [0] * (n + 1)
	for i in range(n):
		iList(v1, n)
		iList(v2, n)
		v1[i] = 1
		time = solve(i, v, n, v1)
		if cmin > time:
			cmin = time
		cmax = max(cmax, time)
	print(cmin, cmax)


for _ in range(int(input())):
	n = int(input())
	v = [int(i) for i in input().split()]
	a = 6
	b = -1
	for i in range(n):
		if i == 0:
			t = 0
			for j in range(i + 1, n):
				if v[j] < v[i]:
					t += 1
			a = min(a, t)
			b = max(b, t)
		elif i == n - 1:
			t = 0
			for j in range(n - 2, -1, -1):
				if v[j] > v[i]:
					t += 1
			a = min(a, t)
			b = max(b, t)
		else:
			t = 0
			ma = max(v[:i + 1])
			mi = min(v[i:])
			for j in range(i + 1, n):
				if v[j] < ma:
					t += 1
			for j in range(i - 1, -1, -1):
				if v[j] > mi:
					t += 1
			a = min(a, t)
			b = max(b, t)
	print(a + 1, b + 1)


T = int(input())
for _ in range(T):
	n = int(input())
	v = list(map(int, input().split()))
	(worst, best) = (1 + n, 1)
	for i in range(n):
		infected = set()
		infected.add(i)
		for j in range(i + 1, n):
			if v[j] < v[i]:
				infected.add(j)
		for j in range(i):
			if v[j] > v[i]:
				infected.add(j)
		for j in range(i + 1, n):
			if j in infected:
				for k in range(i):
					if v[k] > v[j]:
						infected.add(k)
		for j in range(i):
			if j in infected:
				for k in range(i + 1, n):
					if v[k] < v[j]:
						infected.add(k)
		worst = min(worst, len(infected))
		best = max(best, len(infected))
	print(worst, best)


for _ in range(int(input())):
	N = int(input())
	_list = list(map(int, input().split()))
	infected = [1] * N
	for i in range(N):
		for j in range(N):
			if j < i:
				if _list[j] > _list[i]:
					infected[i] += 1
				elif _list[j] <= _list[i] and any((x < _list[j] for x in _list[i:])):
					infected[i] += 1
			if j > i:
				if _list[j] < _list[i]:
					infected[i] += 1
				elif _list[j] >= _list[i] and any((x > _list[j] for x in _list[:i])):
					infected[i] += 1
	print(min(infected), max(infected))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	for i in range(0, n):
		vis = [0] * n
		vis[i] = 1
		mx = mi = a[i]
		for j in range(i):
			if vis[j] == 0 and a[j] > a[i]:
				mx = max(mx, a[j])
				vis[j] = 1
		for j in range(i + 1, n):
			if vis[j] == 0 and a[j] < mx:
				mi = min(mi, a[j])
				vis[j] = 1
		for j in range(i):
			if vis[j] == 0 and a[j] > mi:
				vis[j] = 1
		for j in range(0, n):
			if vis[j] == 1:
				ans[i] += 1
	print(min(ans), max(ans))


for _ in range(int(input())):
	num = int(input())
	res = []
	lis = list(map(int, input().split()))
	for j in range(num):
		c = 1
		min_infected = lis[j]
		max_infected = lis[j]
		for k in range(j + 1, num):
			if lis[j] > lis[k]:
				if min_infected > lis[k]:
					min_infected = lis[k]
		for i in range(0, j):
			if lis[i] > lis[j]:
				if max_infected < lis[i]:
					max_infected = lis[i]
			if lis[i] > min_infected:
				c += 1
		for x in range(j + 1, num):
			if lis[x] < max_infected:
				c += 1
		res.append(c)
	print(min(res), max(res))


def check(i, t):
	inf[i] = 1
	for k in range(i + 1, n):
		if v[i] > v[k] and inf[k] == 0 and ((k - i) / (v[i] - v[k]) > t):
			inf[k] = 1
			check(k, (k - i) / (v[i] - v[k]))
	for k in range(i):
		if v[k] > v[i] and inf[k] == 0 and ((i - k) / (v[k] - v[i]) > t):
			inf[k] = 1
			check(k, (k - i) / (v[i] - v[k]))
	return inf.count(1)
te = int(input())
for j in range(te):
	n = int(input())
	v = list(map(int, input().split()))
	(min, max) = (10, 1)
	t = 0
	for i in range(n):
		inf = [0] * n
		cnt = check(i, t)
		if cnt < min:
			min = cnt
		if cnt > max:
			max = cnt
	print(min, max)


for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	t = []
	for i in range(len(v)):
		for j in range(i + 1, len(v)):
			if v[j] < v[i]:
				t.append(((j - i) / (v[i] - v[j]), i, j))
	t.sort()
	(mx, mn) = (1, n)
	for k in range(len(v)):
		s = set([k])
		for (ti, i, j) in t:
			if i in s or j in s:
				s.add(i)
				s.add(j)
		mx = max(mx, len(s))
		mn = min(mn, len(s))
	print(mn, mx)


def recursion(a, s, p, n, t):
	for i in range(n):
		if a[p][i] > t:
			s.add(i)
			recursion(a, s, i, n, a[p][i])

def solve(n, v):
	time = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			if v[i] == v[j]:
				time[i][j] = -1
			else:
				t = (i - j) / (v[j] - v[i])
				if t <= 0:
					time[i][j] = -1
				else:
					time[i][j] = t
	ss = []
	for i in range(n):
		s = set([i])
		recursion(time, s, i, n, 0)
		ss.append(len(s))
	print(min(ss), max(ss))
for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	solve(n, v)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	M = [[-1 for i in range(n)] for j in range(n)]
	for i in range(n):
		for j in range(n):
			if i != j and a[i] != a[j]:
				if (j - i) / (a[i] - a[j]) >= 0:
					M[i][j] = (j - i) / (a[i] - a[j])
	minimum = float('inf')
	maximum = 0
	for i in range(n):
		c = 0
		visited = [False for j in range(n)]
		Q = list()
		TQ = list()
		Q.append(i)
		visited[i] = True
		TQ.append(0)
		c += 1
		while Q:
			node = Q.pop(0)
			timenode = TQ.pop(0)
			for k in range(n):
				if M[node][k] >= timenode:
					if not visited[k]:
						Q.append(k)
						TQ.append(M[node][k])
						c += 1
						visited[k] = True
		minimum = min(minimum, c)
		maximum = max(maximum, c)
	print(minimum, maximum)


tc = int(input())
for TESTcases in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		temp = []
		for j in range(n):
			if i == j or a[i] == a[j]:
				temp.append(-1)
			else:
				t = (i - j) / (a[j] - a[i])
				temp.append(t)
		b.append(temp)
	ans = []
	for i in range(n):
		arr = []
		booll = [0] * (n + 1)
		booll[i] = 1
		for j in range(n):
			if b[i][j] > 0:
				arr_temp = []
				booll[j] = 1
				arr_temp.append(j)
				arr_temp.append(b[i][j])
				arr.append(arr_temp)
		while 1:
			temp = {}
			for j in arr:
				for k in range(n):
					if b[j[0]][k] >= j[1] and booll[k] == 0:
						booll[k] = 1
						arr_temp = []
						arr_temp.append(k)
						arr_temp.append(b[j[0]][k])
						if k in temp.keys():
							if temp[k] > b[j[0]][k]:
								temp[k] = b[j[0]][k]
						else:
							temp[k] = b[j[0]][k]
			temp2 = []
			for i in temp.keys():
				array = []
				array.append(i)
				array.append(temp[i])
				temp2.append(array)
			if len(temp2) == 0:
				ans.append(booll.count(1))
				break
			arr = temp2
	print(min(ans), max(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	ans = [1 for i in range(n)]
	for i in range(n):
		minimum = min(v[i:])
		maximum = max(v[:i + 1])
		for j in range(i):
			if v[j] > minimum:
				ans[i] += 1
		for j in range(i + 1, n):
			if v[j] < maximum:
				ans[i] += 1
	print(min(ans), max(ans))


t1 = int(input())
while t1 > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	(best1, worst1) = (n, 1)
	for i in range(n):
		temp = [0] * n
		temp[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				temp[j] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, n):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, n):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		c = temp.count(1)
		worst1 = max(c, worst1)
		best1 = min(c, best1)
	print(best1, worst1)
	t1 -= 1


def fi(i, v, n, ied):
	answer = 1
	inf = 1
	for j in range(n):
		if v[j] == v[i] or j == i:
			continue
		tm = float(i - j) / float(v[j] - v[i])
		if tm >= mm[i] and ied[j] == 0:
			inf += 1
			ied[j] = 1
			mm[j] = tm
			answer += fi(j, v, n, ied)
	return answer

def sz(l, n):
	for i in range(n + 1):
		l[i] = 0
	for j in range(12):
		pass
t = int(input())
for _ in range(t):
	minimm = 1000000000
	maximm = -1000000000
	n = int(input())
	v = [int(x) for x in input().split()]
	ied = []
	mm = []
	ied = [0] * (n + 1)
	mm = [0] * (n + 1)
	for i in range(n):
		sz(ied, n)
		sz(mm, n)
		ied[i] = 1
		res = fi(i, v, n, ied)
		if minimm > res:
			minimm = res
		maximm = max(maximm, res)
	print(minimm, end=' ')
	print(maximm)


test = int(input())
for i in range(test):
	N = int(input())
	vel = list(map(int, input().split()))
	res = list()
	for j in range(N):
		d = [vel[j]]
		x = vel[j]
		c = 1
		for k in range(j + 1, N):
			if x > vel[k]:
				d.append(vel[k])
				c += 1
		w = min(d)
		z = 0
		for p in range(j):
			if vel[p] > w:
				c += 1
			if vel[p] > z:
				z = vel[p]
		for qq in range(j + 1, N):
			if vel[qq] >= vel[j] and vel[qq] < z:
				c += 1
		res.append(c)
	print(min(res), max(res))


test = int(input())
while test > 0:
	n = int(input())
	list1 = [int(x) for x in input().split()]
	w = 1
	be = n
	for j in range(n):
		t = [0] * n
		t[j] = 1
		for i in range(j):
			if list1[i] > list1[j]:
				t[i] = 1
		for i in range(j + 1, n):
			if list1[i] < list1[j]:
				t[i] = 1
		for i in range(j):
			if t[i] == 1:
				for k in range(j, n):
					if list1[k] < list1[i]:
						t[k] = 1
		for i in range(j + 1, n):
			if t[i] == 1:
				for k in range(j):
					if list1[i] < list1[k]:
						t[k] = 1
		count = t.count(1)
		w = max(count, w)
		be = min(count, be)
	print(be, w)
	test -= 1


def fun(b, n, t, k):
	c = 1
	for (key, value) in b[n - 1].items():
		if value > t and key not in k:
			k.add(key)
			c += fun(b, key, value, k)
	return c
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [{}, {}, {}, {}, {}]
	for i in range(1, n):
		d = {}
		for j in range(i + 1, n + 1):
			if a[i - 1] - a[j - 1] <= 0:
				continue
			t = (j - i) / (a[i - 1] - a[j - 1])
			b[i - 1][j] = t
			b[j - 1][i] = t
	res = []
	for i in range(n):
		k = set()
		k.add(i + 1)
		res.append(fun(b, i + 1, 0, k))
	print(min(res), max(res))


import sys

def corona(i, a, t, n, v):
	for j in range(n):
		if v[j] == v[i]:
			continue
		x = i - j
		y = v[j] - v[i]
		z = x / y
		if z > t and (not a[j]):
			a[j] = 1
			corona(j, a, z, n, v)
t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	v = list(map(float, input().split()))
	min = sys.maxsize
	max = -sys.maxsize - 1
	a = []
	for i in range(n):
		k = 0
		a = [0] * (n + 1)
		a[i] = 1
		corona(i, a, 0, n, v)
		for j in range(n):
			if a[j]:
				k += 1
		if min > k:
			min = k
		if max < k:
			max = k
	print(min, end=' ')
	print(max)


tc = int(input())
while tc > 0:
	num = int(input())
	l = [int(x) for x in input().split()]
	(best, worst) = (num, 1)
	for i in range(num):
		temp = [0] * num
		temp[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				temp[j] = 1
		for j in range(i + 1, num):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, num):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, num):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		cnt = temp.count(1)
		worst = max(cnt, worst)
		best = min(cnt, best)
	print(best, worst)
	tc -= 1
mod = 1000000007

def power(a, b):
	if b == 0:
		return 1
	ret = power(a, b // 2) % mod
	ret = ret * ret % mod
	if b % 2 != 0:
		ret = ret * a % mod
	return ret

def divide(a, b):
	return a % mod * (power(b, mod - 2) % mod) % mod

def comb(num, res):
	ret = 1
	k = min(res, num - res)
	for i in range(k):
		ret = ret % mod * (num - i) % mod % mod
		ret = divide(ret, i + 1)
	return ret % mod


t1 = int(input())
while t1 > 0:
	n1 = int(input())
	l1 = [int(x1) for x1 in input().split()]
	(best, worst) = (n1, 1)
	for i1 in range(n1):
		temp = [0] * n1
		temp[i1] = 1
		for j1 in range(i1):
			if l1[j1] > l1[i1]:
				temp[j1] = 1
		for j1 in range(i1 + 1, n1):
			if l1[j1] < l1[i1]:
				temp[j1] = 1
		for j1 in range(i1):
			if temp[j1] == 1:
				for k1 in range(i1, n1):
					if l1[k1] < l1[j1]:
						temp[k1] = 1
		for j1 in range(i1 + 1, n1):
			if temp[j1] == 1:
				for k1 in range(i1):
					if l1[j1] < l1[k1]:
						temp[k1] = 1
		c1 = temp.count(1)
		worst = max(c1, worst)
		best = min(c1, best)
	print(best, worst)
	t1 -= 1


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	(best, worst) = (n, 1)
	for i in range(n):
		temp = [0] * n
		temp[i] = 1
		for j in range(i):
			if l[j] > l[i]:
				temp[j] = 1
		for j in range(i + 1, n):
			if l[j] < l[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, n):
					if l[k] < l[j]:
						temp[k] = 1
		for j in range(i + 1, n):
			if temp[j] == 1:
				for k in range(i):
					if l[j] < l[k]:
						temp[k] = 1
		c = temp.count(1)
		worst = max(c, worst)
		best = min(c, best)
	print(best, worst)
	t -= 1
mod = 1000000007

def power(a, b):
	if b == 0:
		return 1
	ret = power(a, b // 2) % mod
	ret = ret * ret % mod
	if b % 2 != 0:
		ret = ret * a % mod
	return ret

def divide(a, b):
	return a % mod * (power(b, mod - 2) % mod) % mod

def comb(n, r):
	ret = 1
	k = min(r, n - r)
	for i in range(k):
		ret = ret % mod * (n - i) % mod % mod
		ret = divide(ret, i + 1)
	return ret % mod


r = int(input())
while r > 0:
	a = int(input())
	m = [int(x) for x in input().split()]
	(best, worst) = (a, 1)
	for i in range(a):
		temp = [0] * a
		temp[i] = 1
		for j in range(i):
			if m[j] > m[i]:
				temp[j] = 1
		for j in range(i + 1, a):
			if m[j] < m[i]:
				temp[j] = 1
		for j in range(i):
			if temp[j] == 1:
				for k in range(i, a):
					if m[k] < m[j]:
						temp[k] = 1
		for j in range(i + 1, a):
			if temp[j] == 1:
				for k in range(i):
					if m[j] < m[k]:
						temp[k] = 1
		s = temp.count(1)
		worst = max(s, worst)
		best = min(s, best)
	print(best, worst)
	r -= 1