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

There are $N$ people on a street (numbered $1$ through $N$). For simplicity, we'll view them as points on a line. For each valid $i$, the position of the $i$-th person is $X_{i}$.

It turns out that exactly one of these people is infected with the virus COVID-19, but we do not know which one. The virus will spread from an infected person to a non-infected person whenever the distance between them is at most $2$. If we wait long enough, a specific set of people (depending on the person that was infected initially) will become infected; let's call the size of this set the *final number of infected people*.

Your task is to find the smallest and largest value of the final number of infected people, i.e. this number in the best and in the 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-seperated integers $X_{1}, X_{2}, \ldots, X_{N}$.

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

------  Constraints ------
$1 ≤ T ≤ 2,000$
$2 ≤ N ≤ 8$
$0 ≤ X_{i} ≤ 10$ for each valid $i$
$X_{1} < X_{2} < \ldots < X_{N}$

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 3$

Subtask #2 (90 points): original constraints

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

2

3 6

3

1 3 5

5

1 2 5 6 7
----- Sample Output 1 ------ 
1 1

3 3

2 3
----- explanation 1 ------ 
Example case 1: The distance between the two people is $3$, so the virus cannot spread and at the end, there will always be only one infected person.

Example case 2: The distance between each two adjacent people is $2$, so all of them will eventually get infected.

Example case 3:
- In one of the best possible scenarios, the person at the position $1$ is infected initially and the virus will also infect the person at the position $2$.
- In one of the worst possible scenarios, the person at the position $5$ is infected initially and the virus will also infect the people at the positions $6$ and $7$.

Source: codechef | Difficulty: EASY
Tags: Amortized analysis

Implementation

Complete search


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	count = 0
	final_array = []
	i = 0
	c = 0
	while i < len(arr) - 1:
		if arr[i + 1] - arr[i] >= 3:
			arr.insert(i + 1, 's')
			i += 2
		else:
			i += 1
	for i in arr:
		if i == 's':
			final_array.append(c)
			c = 0
		else:
			c += 1
	final_array.append(c)
	print(min(final_array), max(final_array))


for _ in range(int(input())):
	x = int(input())
	lis = list(map(int, input().split()))
	a = []
	b = []
	c = 0
	i = 0
	while i < len(lis) - 1:
		if lis[i + 1] - lis[i] >= 3:
			lis.insert(i + 1, 's')
			i += 2
		else:
			i += 1
	for data in lis:
		if data == 's':
			b.append(c)
			c = 0
		else:
			c += 1
	b.append(c)
	print(min(b), max(b))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[i + 1] - a[i] for i in range(n - 1)]
	temp = max_count = 1
	min_count = n
	for i in range(n - 1):
		if b[i] <= 2:
			temp += 1
		else:
			if temp > max_count:
				max_count = temp
			if temp < min_count:
				min_count = temp
			temp = 1
	if temp > max_count:
		max_count = temp
	if temp < min_count:
		min_count = temp
	print(min_count, max_count)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	diff = [x[i + 1] - x[i] for i in range(n - 1)]
	tmp = max_count = 1
	min_count = n
	for i in range(n - 1):
		if diff[i] <= 2:
			tmp += 1
		else:
			if tmp > max_count:
				max_count = tmp
			if tmp < min_count:
				min_count = tmp
			tmp = 1
	if tmp > max_count:
		max_count = tmp
	if tmp < min_count:
		min_count = tmp
	print(min_count, max_count)


for t in range(int(input())):
	n = int(input())
	ppl = list(map(int, input().split()))
	dist = [ppl[i + 1] - ppl[i] for i in range(n - 1)]
	dist_2 = []
	count1 = 0
	for i in range(len(dist)):
		if dist[i] <= 2:
			count1 += 1
		else:
			dist_2.append(count1)
			count1 = 0
	else:
		dist_2.append(count1)
	print(min(dist_2) + 1, max(dist_2) + 1)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	l = list((x[i + 1] - x[i] for i in range(n - 1)))
	lp = []
	c = 0
	for i in range(len(l)):
		if l[i] <= 2:
			c += 1
		else:
			lp.append(c)
			c = 0
	else:
		lp.append(c)
	print(min(lp) + 1, max(lp) + 1)


test = int(input())
for i in range(test):
	number = int(input())
	List = list(map(int, input().split()))
	count = 1
	mini = number
	maxi = 1
	for i in range(1, number):
		if List[i] - List[i - 1] <= 2:
			count += 1
		else:
			mini = min(count, mini)
			maxi = max(count, maxi)
			count = 1
	mini = min(count, mini)
	maxi = max(count, maxi)
	print(mini, maxi)


for _ in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split()]
	count = 1
	minCount = 999
	maxCount = -1
	for i in range(n - 1):
		if nums[i + 1] - nums[i] <= 2:
			count += 1
		else:
			minCount = min(count, minCount)
			maxCount = max(count, maxCount)
			count = 1
	minCount = min(count, minCount)
	maxCount = max(count, maxCount)
	print(minCount, maxCount)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	c1 = 1
	mini = 999
	maxi = -1
	for i in range(n - 1):
		if a[i + 1] - a[i] <= 2:
			c1 += 1
		else:
			mini = min(c1, mini)
			maxi = max(c1, maxi)
			c1 = 1
	mini = min(c1, mini)
	maxi = max(c1, maxi)
	print(mini, maxi)


for _ in range(int(input())):
	x = int(input())
	lis = list(map(int, input().split()))
	b1 = []
	c1 = 0
	i = 0
	while i < len(lis) - 1:
		if lis[i + 1] - lis[i] >= 3:
			lis.insert(i + 1, 's')
			i += 2
		else:
			i += 1
	for data in lis:
		if data == 's':
			b1.append(c1)
			c1 = 0
		else:
			c1 += 1
	b1.append(c1)
	print(min(b1), max(b1))


t = int(input())
for i in range(t):
	res = []
	l = []
	n = int(input())
	count = 1
	mini = n
	maxi = 1
	l = list(map(int, input().split()))
	for i in range(1, n):
		if l[i] - l[i - 1] <= 2:
			count += 1
		else:
			mini = min(count, mini)
			maxi = max(count, maxi)
			count = 1
	mini = min(count, mini)
	maxi = max(count, maxi)
	print(mini, ' ', maxi)


import sys
for line in sys.stdin:
	t = int(line.strip())
	for _ in range(t):
		n = int(sys.stdin.readline().strip())
		v = list(map(int, sys.stdin.readline().strip().split()))
		(mini, maxi, count) = (float('inf'), float('-inf'), 1)
		for i in range(n - 1):
			temp = abs(v[i + 1] - v[i])
			if temp <= 2:
				count += 1
			else:
				mini = min(mini, count)
				maxi = max(maxi, count)
				count = 1
		mini = min(mini, count)
		maxi = max(maxi, count)
		print(mini, maxi)


for z in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	b = []
	i = 0
	c = 0
	while i < len(l) - 1:
		if l[i + 1] - l[i] >= 3:
			l.insert(i + 1, 's')
			i += 2
		else:
			i += 1
	for data in l:
		if data == 's':
			b.append(c)
			c = 0
		else:
			c += 1
	b.append(c)
	print(min(b), max(b))


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	mincount = n
	maxcount = 1
	currcount = 1
	for i in range(1, n):
		if x[i] - x[i - 1] <= 2:
			currcount = currcount + 1
		else:
			if currcount > maxcount:
				maxcount = currcount
			if currcount < mincount:
				mincount = currcount
			currcount = 1
			i = i + 1
	if currcount > maxcount:
		maxcount = currcount
	if currcount < mincount:
		mincount = currcount
	print(mincount, maxcount)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1, 1)
	elif n == 2:
		if abs(l[0] - l[1]) <= 2:
			print(2, 2)
		else:
			print(1, 1)
	else:
		k = []
		for i in range(1, n):
			k.append(abs(l[i - 1] - l[i]))
		count = []
		c = 0
		for i in k:
			if i <= 2:
				c = c + 1
			else:
				count.append(c)
				c = 0
		count.append(c)
		if len(count) == 1:
			print(count[0] + 1, count[0] + 1)
		else:
			m1 = min(count)
			m2 = max(count)
			print(m1 + 1, m2 + 1)


for _ in range(int(input())):
	n = int(input())
	X = list(map(int, input().split()))
	list1 = []
	count = 1
	for i in range(len(X) - 1):
		if X[i + 1] - X[i] <= 2:
			count += 1
		else:
			list1.append(count)
			count = 1
	list1.append(count)
	print(min(list1), max(list1))


for x in range(int(input())):
	N = input()
	l = list(map(int, input().split()))
	n = []
	count = 1
	for x in range(1, len(l)):
		if l[x] - l[x - 1] > 2:
			n.append(count)
			count = 1
		else:
			count += 1
	n.append(count)
	print(min(n), max(n))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	c = 1
	for i in range(len(l) - 1):
		if l[i + 1] - l[i] <= 2:
			c += 1
		else:
			l1.append(c)
			c = 1
	l1.append(c)
	print(min(l1), max(l1))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	c = 1
	for i in range(1, n):
		if l[i] - l[i - 1] <= 2:
			c = c + 1
		else:
			a.append(c)
			c = 1
	a.append(c)
	print(min(a), max(a))


def infect(lst, k):
	h = lst.index(k)
	g = [lst[h]]
	if h > 0:
		for i in range(lst.index(k) - 1, -1, -1):
			if lst[h] - lst[i] <= 2 and lst[h] - lst[i] >= 0:
				g = [lst[h - 1]] + g
				h = h - 1
			else:
				break
	h = lst.index(k)
	if h < len(lst) - 1:
		for i in range(h + 1, len(lst)):
			if lst[i] - lst[h] <= 2 and lst[i] - lst[h] >= 0:
				g = g + [lst[h + 1]]
				h = h + 1
			else:
				break
	return g

def check(lst, j):
	g = True
	for i in lst:
		if j in i:
			g = False
			break
	return g
b = int(input())
for i in range(b):
	N = int(input())
	a = list(map(int, input().split()))
	k = [infect(a, a[0])]
	v = 0
	m = len(k[0])
	for i in a:
		if check(k, i) == True:
			k = k + [infect(a, i)]
	for i in k:
		if len(i) > v:
			v = len(i)
	for i in k:
		if len(i) < m:
			m = len(i)
	print(m, v)


T = int(input())
for cases in range(0, T):
	N = int(input())
	Xi = [int(xi) for xi in input().split()]
	Xi.sort()
	t = 0
	m = Xi[-1]
	f = Xi.index(m)
	emptylist = []
	count = 1
	worstcase = 0
	bestcase = 100
	for i in Xi:
		if t + 1 <= f:
			nextel = Xi[t + 1]
			t += 1
			diff = nextel - i
			emptylist.append(diff)
	for y in emptylist:
		if y <= 2:
			count += 1
		else:
			if count > worstcase:
				worstcase = count
			if count < bestcase:
				bestcase = count
			count = 1
	if count > worstcase:
		worstcase = count
	if count < bestcase:
		bestcase = count
	print(bestcase, worstcase)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	d = []
	c = 1
	for i in range(a - 1):
		if b[i + 1] - b[i] <= 2:
			c = c + 1
		else:
			d.append(c)
			c = 1
	d.append(c)
	print(min(d), max(d))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = [1]
	for i in range(1, n):
		if l[i] - l[i - 1] < 3:
			r[-1] += 1
		else:
			r.append(1)
	print(min(r), max(r))


for i in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for j in range(0, len(l)):
		k = l[j]
		t = 1
		for h in range(j + 1, len(l)):
			if abs(l[h] - l[h - 1]) <= 2:
				t = t + 1
				continue
			else:
				break
		for r in range(j - 1, -1, -1):
			if abs(l[r] - l[r + 1]) <= 2:
				t = t + 1
				continue
			else:
				break
		a.append(t)
	print(min(a), ' ', max(a))


for i in range(int(input())):
	n = int(input())
	lt = list(map(int, input().split()))
	c = 1
	lt1 = []
	for i in range(len(lt) - 1):
		if lt[i + 1] - lt[i] <= 2:
			c += 1
		else:
			lt1.append(c)
			c = 1
		if i == len(lt) - 2:
			lt1.append(c)
	print(min(lt1), max(lt1))


t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	min = n
	max = 0
	for i in range(n - 1):
		if a[i + 1] - a[i] <= 2:
			c = c + 1
		else:
			if c < min:
				min = c
			if c > max:
				max = c
			c = 1
	if c < min:
		min = c
	if c > max:
		max = c
	print(min, '', max)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(ml, mi, c, f) = (1, 1, 1, 0)
	for i in range(1, n):
		d = abs(l[i] - l[i - 1])
		if d <= 2:
			c += 1
		else:
			if mi > c or f == 0:
				mi = c
			if ml < c:
				ml = c
			f = 1
			c = 1
	if mi > c or f == 0:
		mi = c
	if ml < c:
		ml = c
	print(mi, ml)


t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	smaller = n
	bigger = 0
	for i in range(n - 1):
		if a[i + 1] - a[i] <= 2:
			c = c + 1
		else:
			if c < smaller:
				smaller = c
			if c > bigger:
				bigger = c
			c = 1
	if c < smaller:
		smaller = c
	if c > bigger:
		bigger = c
	print(smaller, '', bigger)


t = int(input())
for el in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	l = [1]
	j = 0
	for i in range(n - 1):
		if a[i + 1] - a[i] <= 2:
			l[j] += 1
		else:
			j += 1
			l.append(1)
	(x, y) = (min(l), max(l))
	print(str(x) + ' ' + str(y))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	mi = float('inf')
	mx = float('-inf')
	count = 1
	for i in range(1, n):
		if lst[i] - lst[i - 1] <= 2:
			count += 1
		else:
			mi = min(count, mi)
			mx = max(mx, count)
			count = 1
	mi = min(mi, count)
	mx = max(mx, count)
	print(mi, mx)


for _ in range(int(input())):
	input()
	L = list(map(int, input().split()))
	count = 1
	worst_case = 1
	best_case = 1
	first_time = 0
	for i in range(len(L) - 1):
		if L[i + 1] - L[i] <= 2:
			count += 1
		else:
			worst_case = max(worst_case, count)
			if first_time == 0:
				best_case = count
				first_time = 1
			else:
				best_case = min(best_case, count)
			count = 1
	worst_case = max(worst_case, count)
	if first_time == 1:
		best_case = min(best_case, count)
	else:
		best_case = count
	print(best_case, worst_case)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	lst = [1]
	j = 0
	for i in range(n - 1):
		if l[i + 1] - l[i] <= 2:
			lst[j] += 1
		else:
			j += 1
			lst.append(1)
	(x, y) = (min(lst), max(lst))
	print(str(x) + ' ' + str(y))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = []
	cnt = 1
	for j in range(len(l) - 1):
		if l[j + 1] - l[j] > 2:
			m.append(cnt)
			cnt = 1
		else:
			cnt += 1
	else:
		m.append(cnt)
	print(min(m), max(m))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = []
	c = 0
	i = 0
	while i < len(l) - 1:
		if l[i + 1] - l[i] >= 3:
			l.insert(i + 1, 'u')
			i += 2
		else:
			i += 1
	for i in l:
		if i == 'u':
			p.append(c)
			c = 0
		else:
			c += 1
	p.append(c)
	print(min(p), max(p))


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	spread = []
	count = 1
	for i in range(n - 1):
		if abs(l[i] - l[i + 1]) <= 2:
			count += 1
		else:
			spread.append(count)
			count = 1
	spread.append(count)
	print(min(spread), max(spread))


a = int(input())
for i in range(a):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	k = []
	for i in range(n - 1):
		if l[i + 1] - l[i] < 3:
			s += 1
		else:
			k.append(s)
			s = 0
	k.append(s)
	print(min(k) + 1, end=' ')
	print(max(k) + 1)


def solve():
	n = int(input())
	A = sorted([int(x) for x in input().split()])
	(maxi, mini) = (0, n)
	(count, prev) = (0, A[0])
	for i in range(n):
		if A[i] - prev <= 2:
			count += 1
		else:
			maxi = max(count, maxi)
			mini = min(count, mini)
			count = 1
		prev = A[i]
	maxi = max(count, maxi)
	mini = min(count, mini)
	print(f'{mini} {maxi}')
T = int(input())
while T:
	solve()
	T -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.append(-100)
	li = []
	count = 1
	for i in range(len(arr) - 1):
		m = abs(arr[i] - arr[i + 1])
		if m <= 2:
			count += 1
		else:
			li.append(count)
			count = 1
	print(min(li), max(li))


for i in range(int(input())):
	n = int(input())
	positions = input().split(' ')
	(distances_l, distances) = ([], 0)
	for j in range(n - 1):
		if int(positions[j + 1]) - int(positions[j]) <= 2:
			distances += 1
		else:
			distances_l.append(distances)
			distances = 0
	else:
		distances_l.append(distances)
	distances_l.sort()
	print(distances_l[0] + 1, distances_l[-1] + 1)


import sys
testcases = int(input())
while testcases > 0:
	N = int(input())
	li = list(map(int, input().split()))[:N]
	count = 1
	ma = -sys.maxsize - 1
	mi = sys.maxsize
	for i in range(N - 1):
		if abs(li[i + 1] - li[i]) <= 2:
			count += 1
		else:
			mi = min(mi, count)
			ma = max(ma, count)
			count = 1
	mi = min(mi, count)
	ma = max(ma, count)
	print(mi, ma)
	testcases -= 1


t = int(input())
for tc in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	x.append(-1000)
	d = []
	a = 1
	for j in range(len(x) - 1):
		if abs(x[j] - x[j + 1]) <= 2:
			a += 1
		else:
			d.append(a)
			a = 1
	print(min(d), max(d))


for i in range(int(input())):
	n = int(input())
	line = list(map(int, input().split()))
	leng = []
	for j in range(1, len(line)):
		leng.append(line[j] - line[j - 1])
	aff = [0]
	for j in leng:
		if j == 2 or j == 1:
			aff[len(aff) - 1] += 1
		else:
			aff.append(0)
	print(f'{min(aff) + 1} {max(aff) + 1}')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.append(-100)
	inf = []
	tot = 1
	for i in range(len(l) - 1):
		if abs(l[i] - l[i + 1]) <= 2:
			tot += 1
		else:
			inf.append(tot)
			tot = 1
	print(min(inf), max(inf))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	record = set()
	c = 1
	for i in range(n):
		if i == n - 1:
			if abs(x[i] - x[i - 1]) > 2:
				record.add(1)
		elif abs(x[i] - x[i + 1]) <= 2:
			c += 1
			if i == n - 2:
				record.add(c)
		else:
			record.add(c)
			c = 1
	print(min(record), max(record))


t = int(input())
res = []
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	islands = []
	start = 0
	for k in range(n):
		if k < n - 1 and li[k + 1] - li[k] > 2:
			islands.append(li[start:k + 1])
			start = k + 1
		if k == n - 1:
			islands.append(li[start:len(li)])
	smIsland = 10
	bigIsland = 0
	for m in range(len(islands)):
		smIsland = min(smIsland, len(islands[m]))
		bigIsland = max(bigIsland, len(islands[m]))
	res.append(str(smIsland) + ' ' + str(bigIsland))
print('\n'.join(res))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = []
	k = 1
	for j in range(n - 1):
		dif = abs(arr[j] - arr[j + 1])
		if dif <= 2:
			k += 1
		else:
			res.append(k)
			k = 1
	res.append(k)
	if len(res) != 0:
		print(min(res), max(res))
	else:
		print(1, 1)


def min_max_inf(n, p):
	i = 0
	mn = 10 ** 5
	mx = 0
	while i < n:
		cr = p[i]
		ci = 1
		while i + 1 < n and cr + 2 >= p[i + 1]:
			cr = p[i + 1]
			ci += 1
			i += 1
		mx = max(mx, ci)
		mn = min(mn, ci)
		i += 1
	print(mn, mx)
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	min_max_inf(n, p)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l1 = []
	for j in range(len(a) - 1):
		l1.append(a[j + 1] - a[j])
	l2 = []
	count = 0
	for ele in l1:
		if ele <= 2:
			count += 1
		else:
			l2.append(count)
			count = 0
	l2.append(count)
	l2.sort()
	max_a = l2[len(l2) - 1] + 1
	print(l2[0] + 1, max_a)


T = int(input())
for i in range(T):
	n = int(input())
	x = list(map(int, input().split()))
	c = 1
	b = []
	for j in range(n - 1):
		if abs(x[j] - x[j + 1]) <= 2:
			c += 1
		else:
			b.append(c)
			c = 1
	b.append(c)
	print(min(b), max(b))


i = int(input())
x = 0
list1 = []
while x < i:
	pp = int(input())
	ss = input().split()
	ss2 = []
	for ele in ss:
		ss2.append(int(ele))
	x = x + 1
	tot = []
	u = 0
	while u < pp - 1:
		p = ss2[u + 1] - ss2[u]
		if p > 2:
			tot.append(u)
		u = u + 1
	tot.append(len(ss2) - 1)
	tot = tot[::-1]
	tot.append(-1)
	tot = tot[::-1]
	bb = 0
	tot2 = []
	while bb < len(tot) - 1:
		tot2.append(tot[bb + 1] - tot[bb])
		bb = bb + 1
	list1.append(str(str(min(tot2)) + ' ' + str(max(tot2))))
for ele in list1:
	print(ele)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	infected = []
	count = []
	c = 1
	for i in range(n - 1):
		infected.append(x[i + 1] - x[i])
	for j in infected:
		if j < 3:
			c += 1
		elif j > 2:
			count.append(c)
			c = 1
	count.append(c)
	print(min(count), max(count))


for _ in range(int(input())):
	a = int(input())
	l1 = sorted([int(x) for x in input().split()])
	(maxi, mini) = (0, a)
	(count, prev) = (0, l1[0])
	for i in range(a):
		if l1[i] - prev <= 2:
			count += 1
		else:
			maxi = max(count, maxi)
			mini = min(count, mini)
			count = 1
		prev = l1[i]
	maxi = max(count, maxi)
	mini = min(count, mini)
	print(mini, maxi)


tc = int(input())
for _ in range(tc):
	n = int(input())
	x = list(map(int, input().split()))
	d = []
	for i in range(n - 1):
		d.append(x[i + 1] - x[i])
	count = 1
	gorb = []
	for i in range(n - 1):
		if d[i] <= 2:
			count += 1
		else:
			gorb.append(count)
			count = 1
		if i == n - 2:
			gorb.append(count)
	print(min(gorb), max(gorb))


test_cases = int(input())

def is_infected(current, target):
	if abs(current - target <= 1):
		return True
	else:
		return False

def in_index(index, lst_len):
	if index < 0 or index > lst_len - 1:
		return False
	else:
		return True
for i in range(test_cases):
	pop_size = int(input())
	population = list(map(int, input().split()))
	max_infects = curr_infects = 1
	min_infects = None
	for strt_ind in range(pop_size):
		up_ind = strt_ind
		while in_index(up_ind + 1, pop_size) and abs(population[up_ind] - population[up_ind + 1]) <= 2:
			up_ind += 1
			curr_infects += 1
		dwn_ind = strt_ind
		while in_index(dwn_ind - 1, pop_size) and abs(population[dwn_ind] - population[dwn_ind - 1]) <= 2:
			dwn_ind -= 1
			curr_infects += 1
		if curr_infects > max_infects:
			max_infects = curr_infects
		if min_infects is None:
			min_infects = curr_infects
		elif curr_infects < min_infects:
			min_infects = curr_infects
		curr_infects = 1
	print(min_infects, max_infects)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted([int(i) for i in input().split()])
	maxi = 0
	mini = n
	count = 0
	pre = a[0]
	for i in range(n):
		if a[i] - pre <= 2:
			count += 1
		else:
			maxi = max(count, maxi)
			mini = min(count, mini)
			count = 1
		pre = a[i]
	maxi = max(count, maxi)
	mini = min(count, mini)
	print(f'{mini} {maxi}')