Oh, New Year. The time to gather all your friends and reflect on the heartwarming events of the past year...

$n$ friends live in a city which can be represented as a number line. The $i$-th friend lives in a house with an integer coordinate $x_i$. The $i$-th friend can come celebrate the New Year to the house with coordinate $x_i-1$, $x_i+1$ or stay at $x_i$. Each friend is allowed to move no more than once.

For all friends $1 \le x_i \le n$ holds, however, they can come to houses with coordinates $0$ and $n+1$ (if their houses are at $1$ or $n$, respectively).

For example, let the initial positions be $x = [1, 2, 4, 4]$. The final ones then can be $[1, 3, 3, 4]$, $[0, 2, 3, 3]$, $[2, 2, 5, 5]$, $[2, 1, 3, 5]$ and so on. The number of occupied houses is the number of distinct positions among the final ones.

So all friends choose the moves they want to perform. After that the number of occupied houses is calculated. What is the minimum and the maximum number of occupied houses can there be?


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of friends.

The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le n$) — the coordinates of the houses of the friends.


-----Output-----

Print two integers — the minimum and the maximum possible number of occupied houses after all moves are performed.


-----Examples-----
Input
4
1 2 4 4

Output
2 4

Input
9
1 1 8 8 8 4 4 4 4

Output
3 8

Input
7
4 3 7 1 4 3 3

Output
3 6



-----Note-----

In the first example friends can go to $[2, 2, 3, 3]$. So friend $1$ goes to $x_1+1$, friend $2$ stays at his house $x_2$, friend $3$ goes to $x_3-1$ and friend $4$ goes to $x_4-1$. $[1, 1, 3, 3]$, $[2, 2, 3, 3]$ or $[2, 2, 4, 4]$ are also all valid options to obtain $2$ occupied houses.

For the maximum number of occupied houses friends can go to $[1, 2, 3, 4]$ or to $[0, 2, 4, 5]$, for example.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
n = int(input())
l = list(map(int, input().split(' ')))
l.sort()
lonly = set(l)
lonly = list(lonly)
lonly.sort()
i = 0
lenonly = len(lonly)
res1 = 0
while i < lenonly:
	if i - 1 >= 0 and lonly[i] - lonly[i - 1] == 1:
		lonly[i] = lonly[i - 1]
	elif i + 1 < lenonly:
		dif = lonly[i + 1] - lonly[i]
		if dif == 1:
			lonly[i] = lonly[i + 1]
			i += 1
		elif dif == 2:
			lonly[i] = lonly[i + 1] = lonly[i] + 1
			i += 1
	i += 1
lonly = set(lonly)
print(len(lonly), end=' ')
last = -1
l2 = set()
for i in l:
	if i == last:
		last = i + 1
		l2.add(last)
	elif i > last:
		if i - 1 != last:
			last = i - 1
			l2.add(last)
		else:
			last = i
			l2.add(last)
print(len(l2))


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
a = list(map(int, input().split()))
ct = [0 for i in range(n + 2)]
for i in a:
	ct[i] += 1
dp = [0 for i in range(n + 2)]
ans = 0
i = 1
while i <= n:
	if ct[i] == 0:
		i += 1
		continue
	ans += 1
	i += 3
dp = [0 for i in range(n + 2)]
ans2 = 0
for i in range(1, n + 1):
	if ct[i] == 0:
		continue
	if ct[i - 1] == 0:
		dp[i - 1] = 1
		ct[i] -= 1
	if ct[i] == 0:
		continue
	if ct[i] == 1:
		dp[i] = 1
		continue
	ct[i + 1] += 1
	dp[i + 1] = 1
	if ct[i] != 0:
		dp[i] = 1
for i in range(n + 2):
	ans2 += dp[i]
print(ans, ans2)


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
import random

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def GI(V, E, Directed=False, index=0):
	org_inp = []
	g = [[] for i in range(n)]
	for i in range(E):
		inp = LI()
		org_inp.append(inp)
		if index == 0:
			inp[0] -= 1
			inp[1] -= 1
		if len(inp) == 2:
			(a, b) = inp
			g[a].append(b)
			if not Directed:
				g[b].append(a)
		elif len(inp) == 3:
			(a, b, c) = inp
			aa = (inp[0], inp[2])
			bb = (inp[1], inp[2])
			g[a].append(bb)
			if not Directed:
				g[b].append(aa)
	return (g, org_inp)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bit % n for bit in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
input = lambda : sys.stdin.readline().rstrip()

def ran_input():
	import random
	n = random.randint(4, 16)
	(rmin, rmax) = (1, 10)
	a = [random.randint(rmin, rmax) for _ in range(n)]
	return (n, a)
show_flg = False
show_flg = True
ans = 0
n = I()
x = sorted(LI())
dm = [0] * (n + 2)
for i in range(n):
	if dm[x[i] - 1] == 0:
		dm[x[i] - 1] = 1
	elif dm[x[i]] == 0:
		dm[x[i]] = 1
	elif dm[x[i] + 1] == 0:
		dm[x[i] + 1] = 1
ans = sum(dm)
dp = [0] * (n + 2)
(j, p) = (0, x[0])
m = 0
for i in range(n):
	if sum(dp[x[i] - 1:x[i] + 1 + 1]) == 0:
		dp[x[i] - 1:x[i] + 1 + 1] = [m + 1] * 3
	m = dp[x[i] - 1]
print(max(dp), ans)


from collections import Counter

def f(a, n):
	cnt = [0] * (n + 2)
	for i in a:
		cnt[i] += 1
	cnt2 = cnt.copy()
	cnt3 = cnt.copy()
	i = 0
	d = 2
	mx = 0
	right = False
	while i < n + 1:
		if cnt[i] == 0:
			d += 1
		else:
			j = i - 1
			s = 0
			while j + 1 < n + 1 and cnt[j + 1]:
				j += 1
				s += cnt[j]
			mx += j - i + 1
			if s > j - i + 1 and (right == False or d > 1):
				s -= 1
				mx += 1
			right = False
			if s > j - i + 1:
				right = True
				mx += 1
			i = j
			d = 0
		i += 1
	cnt = cnt2
	for i in sorted(a):
		if cnt[i] > 1:
			if cnt[i - 1] == 0:
				cnt[i - 1] += 1
				cnt[i] -= 1
			if cnt[i + 1] == 0 and cnt[i] > 1:
				cnt[i + 1] += 1
				cnt[i] -= 1
			if cnt[i] > 1:
				cnt[i + 1] += cnt[i] - 1
				cnt[i] = 1
	mx = max(mx, n + 2 - cnt.count(0))
	l = sorted(list(set(a)))
	if len(l) == 1:
		return (1, mx)
	i = 0
	mn = 0
	cnt = cnt3
	while i < n + 1:
		if cnt[i] == 0:
			i += 1
		else:
			mn += 1
			i += 3
	return (mn, mx)
n = int(input())
a = list(map(int, input().strip().split()))
print(*f(a, n))


n = int(input())
x = list(map(int, input().split()))
x.sort()
flag = [False] * (n + 2)
for xi in x:
	if not flag[xi - 1]:
		flag[xi - 1] = True
	elif not flag[xi]:
		flag[xi] = True
	else:
		flag[xi + 1] = True
ans1 = flag.count(True)
x = list(set(x))
flag = [False] * (n + 2)
for xi in x:
	if flag[xi - 1] or flag[xi]:
		continue
	else:
		flag[xi + 1] = True
ans0 = flag.count(True)
print(ans0, ans1)


import sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
xs = list(map(int, input().split()))
xs.sort()
i = 0
mx = 0
prev = -2
while i < n:
	l = xs[i]
	ctr = 1
	while i < n - 1 and xs[i + 1] <= xs[i] + 1:
		i += 1
		ctr += 1
	r = xs[i]
	w = r - l + 1
	if w == ctr:
		mx += w
	elif w + 1 == ctr:
		mx += w + 1
		if prev == l - 1:
			prev = r + 1
	else:
		if prev < l - 1:
			mx += w + 2
		else:
			mx += w + 1
		prev = r + 1
	i += 1
mn = 0
i = 0
prev = -2
while i < n:
	l = xs[i]
	while i < n - 1 and xs[i + 1] <= xs[i] + 1:
		i += 1
	r = xs[i]
	if prev == l - 1:
		l += 1
		if l > r:
			i += 1
			continue
	w = r - l + 1
	if w > 1:
		mn += (w - 1) // 3 + 1
		if w % 3 == 1:
			prev = r + 1
	else:
		mn += 1
		prev = r + 1
	i += 1
print(mn, mx)


n = int(input())
X = [0] * (n + 2)
Y = [0] * (n + 2)
xx = [int(x) for x in input().strip().split()]
for a in xx:
	X[a] += 1
	Y[a + 1] += 1
for i in range(n):
	if Y[i] == 0:
		if Y[i + 1] > 0:
			Y[i + 1] -= 1
			Y[i] = 1
		elif Y[i + 2] > 0:
			Y[i + 2] -= 1
			Y[i] = 1
if Y[n] == 0 and Y[n + 1] > 1:
	Y[n] = 1
	Y[n + 1] -= 1
i = 0
while i < n:
	if X[i] > 0 and X[i + 2] > 0:
		X[i] = 0
		X[i + 1] += X[i] + X[i + 2]
		X[i + 2] = 0
		i = i + 3
	elif X[i] > 0 and X[i + 1] > 0 and (X[i + 2] == 0):
		X[i] += X[i + 1]
		X[i + 1] = 0
		i = i + 2
	else:
		i = i + 1
maxv = len(Y) - Y.count(0)
minv = len(X) - X.count(0)
print(minv, maxv)


n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 2)
c = [0] * (n + 2)
for i in range(n):
	c[a[i]] += 1
	b[a[i]] = 1
for i in range(len(c) - 1):
	if c[i] == 0 and c[i + 1] > 0:
		c[i] = 1
		c[i + 1] -= 1
for i in range(len(c) - 1, 0, -1):
	if c[i] == 0 and c[i - 1] > 0:
		c[i] = 1
		c[i - 1] -= 1
ans = 0
x = 1
dp = [[0] * 3 for i in range(n + 2)]
(dp[1][0], dp[1][1], dp[1][2]) = (b[1], b[1], b[1])
for i in range(2, len(dp)):
	x = 0
	if b[i - 1] + b[i - 2] == 0:
		x = 1
	if b[i] == 1:
		dp[i][0] = min(dp[i - 1]) + 1
		dp[i][1] = min(dp[i - 1][0] + (b[i - 1] + 1) % 2, dp[i - 1][2] + x)
		dp[i][2] = dp[i - 1][0] - b[i - 1] + 1
	else:
		dp[i][0] = min(dp[i - 1])
		dp[i][1] = min(dp[i - 1])
		dp[i][2] = dp[i - 1][0]
print(min(dp[-1]), len(c) - c.count(0))


n = int(input())
l = list(map(int, input().split()))
l.sort()
ll = l.copy()
up = 1
left = l[0]
for i in range(n):
	if l[i] > left + 2:
		left = l[i]
		up += 1
ll[0] -= 1
for i in range(1, n - 1):
	if ll[i - 1] == ll[i]:
		if ll[i] != ll[i + 1]:
			ll[i] += 1
	elif ll[i - 1] == ll[i] - 1:
		continue
	else:
		ll[i] -= 1
ll[n - 1] += 1
d = {}
for i in ll:
	d[i] = 0
najw = len(d)
print(up, najw)


from random import *
n = int(input())
arr = list(map(int, input().split()))

def solve(n, arr):
	cords = [0] + [0 for i in range(n)] + [0]
	for x in arr:
		cords[x] += 1
	mn = 100000000
	ss = 0
	for i in range(len(cords)):
		if cords[i]:
			ss += 1
	ncords = cords[:]
	i = 1
	while i < n + 1:
		if not ncords[i]:
			i += 1
			continue
		ncords[i + 1] += ncords[i]
		ncords[i] = 0
		if i + 2 <= n + 1:
			ncords[i + 1] += ncords[i + 2]
			ncords[i + 2] = 0
			i += 3
		else:
			i += 2
	s = 0
	for i in range(len(ncords)):
		if ncords[i]:
			s += 1
	print(s, end=' ')
	ncords = cords[:]
	l = 1
	r = n

	def work_l():
		if ncords[l] == 0:
			return
		elif ncords[l] == 1:
			if ncords[l - 1] == 0:
				ncords[l - 1] = 1
				ncords[l] = 0
			return
		elif ncords[l] == 2:
			if ncords[l - 1] == 0:
				ncords[l - 1] += 1
				ncords[l] -= 1
				return
			else:
				ncords[l + 1] += 1
				ncords[l] -= 1
				return
		else:
			ncords[l - 1] += 1
			ncords[l + 1] += 1
			ncords[l] -= 2
			return

	def work_r():
		if ncords[r] == 0:
			return
		elif ncords[r] == 1:
			if ncords[r + 1] == 0:
				ncords[r + 1] = 1
				ncords[r] = 0
			return
		elif ncords[r] == 2:
			if ncords[r + 1] == 0:
				ncords[r + 1] += 1
				ncords[r] -= 1
				return
			else:
				ncords[r - 1] += 1
				ncords[r] -= 1
				return
		else:
			ncords[r - 1] += 1
			ncords[r + 1] += 1
			ncords[r] -= 2
			return
	while l < r:
		work_l()
		l += 1
		if l == r:
			break
		work_r()
		r -= 1
	work_l()
	s = 0
	for i in range(len(ncords)):
		if ncords[i]:
			s += 1
	print(s)
solve(n, arr)


import sys
input = sys.stdin.readline
n = int(input())
x = list(map(int, input().split()))
y = [0] * (n + 5)
for i in x:
	y[i] += 1
ans1 = 0
r = -1
for i in range(n + 5):
	if i <= r:
		continue
	if y[i]:
		r = i + 2
		ans1 += 1
ans2 = 0
(cnt, l) = (0, 0)
(f, s) = (0, -1)
for i in range(n + 5):
	if y[i]:
		if not f:
			f = 1
			s = i
		cnt += y[i]
		l += 1
	else:
		if not f:
			continue
		ans2 += l
		if cnt - l == 1:
			if not y[s - 1]:
				y[s - 1] += 1
				ans2 += 1
			else:
				y[i] += 1
				ans2 += 1
		elif cnt - l >= 2:
			if not y[s - 1]:
				y[s - 1] += 1
				ans2 += 1
			y[i] += 1
			ans2 += 1
		f = 0
		(cnt, l) = (0, 0)
print(ans1, ans2)


import sys
LI = lambda : list(map(int, sys.stdin.readline().strip('\n').split()))
MI = lambda : map(int, sys.stdin.readline().strip('\n').split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline().strip('\n'))
n = II()
a = sorted(LI())
mn = 1
p = set([a[0] - 1, a[0], a[0] + 1])
ln = [0] * (n + 2)
ln[a[0] - 1] = 1
for v in a[1:]:
	if not ln[v - 1]:
		ln[v - 1] = 1
	elif not ln[v]:
		ln[v] = 1
	elif not ln[v + 1]:
		ln[v + 1] = 1
	c = set([v - 1, v, v + 1])
	p = p.intersection(c)
	if not p:
		mn += 1
		p = c.copy()
print(mn, sum(ln))


import sys, collections
N = int(sys.stdin.readline().strip())
F = [int(i) for i in sys.stdin.readline().strip().split(' ')]
F = sorted(F)
size = 2 * 10 ** 5
MIN = [False] * (size + 2)
MAX = [False] * (size + 2)
for f in F:
	if MIN[f - 1] or MIN[f] or MIN[f + 1]:
		None
	else:
		MIN[f + 1] = True
	if not MAX[f - 1]:
		MAX[f - 1] = True
	elif not MAX[f]:
		MAX[f] = True
	else:
		MAX[f + 1] = True
print('{} {}'.format(sum(MIN), sum(MAX)))


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
A.sort()
B = {A[0] - 1}
C = {A[0] + 1}
for i in range(1, n):
	if A[i] - 1 in B and A[i] in B:
		B.add(A[i] + 1)
	elif A[i] - 1 in B:
		B.add(A[i])
	else:
		B.add(A[i] - 1)
	if A[i] - 1 in C or A[i] in C:
		continue
	else:
		C.add(A[i] + 1)
print(len(C), len(B))


n = int(input())
d = {}
a = list(map(int, input().split()))
a.sort()
for i in a:
	d[i] = d.get(i, 0) + 1
b = list(d.keys())
b.sort()
ind = b[0]
mi = 0
i = ind
while i < n + 1:
	if i in d:
		mi += 1
		i += 2
	i += 1
ma = [0] * (n + 2)
for i in b:
	if d[i] == 1:
		if ma[i - 1] == 0:
			ma[i - 1] = 1
		elif ma[i] == 0:
			ma[i] = 1
		else:
			ma[i + 1] = 1
	elif d[i] == 2:
		f = 2
		if ma[i - 1] == 0:
			ma[i - 1] = 1
			f -= 1
		if ma[i] == 0:
			ma[i] = 1
			f -= 1
		if f:
			ma[i + 1] = 1
			f -= 1
	else:
		ma[i + 1] = 1
		ma[i] = 1
		ma[i - 1] = 1
print(mi, sum(ma))


n = int(input())
arr = [int(z) for z in input().split()]
ppl = [0] * (n + 2)
mintaken = [False] * (n + 2)
maxtaken = [False] * (n + 2)
for i in arr:
	ppl[i] += 1
(minimum, maximum) = (0, 0)
for i in range(1, n + 1):
	if ppl[i] > 0:
		if mintaken[i - 1] == False and mintaken[i] == False:
			minimum += 1
			mintaken[i + 1] = True
		if ppl[i] > 0 and (not maxtaken[i - 1]):
			maxtaken[i - 1] = True
			ppl[i] -= 1
			maximum += 1
		if ppl[i] > 0 and (not maxtaken[i]):
			maxtaken[i] = True
			ppl[i] -= 1
			maximum += 1
		if ppl[i] > 0 and (not maxtaken[i + 1]):
			maxtaken[i + 1] = True
			ppl[i] -= 1
			maximum += 1
print(minimum, maximum)


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
C = Counter(A)

def check1(C):
	C2 = [0] * (N + 2)
	i = 0
	while i < N + 2:
		if C[i] > 0 and (C[i + 1] > 0 or C[i + 2] > 0):
			C2[i + 1] = C[i] + C[i + 1] + C[i + 2]
			C[i] = C[i + 1] = C[i + 2] = 0
			i += 3
		else:
			C2[i] = C[i]
			C[i] = 0
			i += 1
	return C2

def check2(C):
	C2 = [0] * (N + 2)
	i = 0
	while i < N:
		if C[i + 1] > 0 and C2[i] == 0:
			C2[i] += 1
			C[i + 1] -= 1
		if C[i + 1] > 0 and C2[i + 1] == 0:
			C2[i + 1] += 1
			C[i + 1] -= 1
		C2[i + 2] += C[i + 1]
		C[i + 1] = 0
		i += 1
	return C2
res1 = check1(C.copy())
res2 = check2(C.copy())
ans1 = N + 2 - res1.count(0)
ans2 = N + 2 - res2.count(0)
print(ans1, ans2)


from collections import deque
import sys
import math
input = sys.stdin.buffer.readline
n = int(input())
blu = [0 for _ in range(2 * 10 ** 5 + 2)]
on = [False for _ in blu]
xx = list(map(int, input().split()))
for z in xx:
	blu[z] += 1
for i in range(1, len(blu)):
	if blu[i] == 0:
		continue
	if on[i - 1] == False:
		on[i - 1] = True
		blu[i] -= 1
	if blu[i] == 0:
		continue
	if on[i] == False:
		on[i] = True
		blu[i] -= 1
	if blu[i] == 0:
		continue
	if on[i + 1] == False:
		on[i + 1] = True
		blu[i] -= 1
upper = 0
v = {True: 1, False: 0}
upper = sum([v[z] for z in on])
xx.sort()
xx.insert(0, -10)
xx.append(10 ** 7)
x = xx.copy()
x2 = []
nnnn = -1
for oo in x:
	if oo != nnnn:
		x2.append(oo)
	nnnn = oo
x = x2
last = -2
for i in range(1, len(x) - 1):
	if x[i] - last > 1:
		x[i] += 1
		last = x[i]
	elif x[i] - last == 1:
		x[i] -= 1
		last = x[i]
s = x[0]
cc = 0
for i in x:
	if i != s:
		cc += 1
	s = i
lower = cc
print(lower - 1, upper)


import string
from collections import defaultdict, Counter
from math import sqrt, log10, log2, log, gcd, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations_with_replacement
import sys, io, os
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = int(pow(10, 7) + 9)
inf = float('inf')

def get_list():
	return [int(i) for i in input().split()]

def yn(a):
	print('YES' if a else 'NO', flush=False)
t = 1
for i in range(t):
	n = int(input())
	l = get_list()
	l.sort()
	seta2 = set()
	for i in l:
		for j in range(i - 1, i + 2):
			if j not in seta2:
				seta2.add(j)
				break
	l = sorted(set(l))
	dict = defaultdict(int)
	for i in l:
		dict[i] = 1
	counter = 0
	for i in range(len(l)):
		if i < len(l) - 2:
			if dict[l[i]] and dict[l[i + 1]] and dict[l[i + 2]]:
				if l[i] + 1 == l[i + 1] == l[i + 2] - 1:
					dict[l[i]] = 0
					dict[l[i + 2]] = 0
		if i != len(l) - 1:
			if dict[l[i]] and dict[l[i + 1]]:
				if l[i] + 2 == l[i + 1]:
					dict[l[i]] = 0
					dict[l[i + 1]] = 0
					counter += 1
		if i != len(l) - 1:
			if dict[l[i]] and dict[l[i + 1]]:
				if l[i] + 1 == l[i + 1]:
					dict[l[i + 1]] = 0
	for i in range(len(l) - 1):
		if dict[l[i]] and dict[l[i + 1]]:
			if l[i] + 1 == l[i + 1]:
				dict[l[i + 1]] = 0
	print(counter + sum([dict[i] for i in l]), len(seta2), flush=False)


from sys import stdin, stdout
n = int(stdin.readline().strip())
friends = list(map(int, stdin.readline().split()))
friends.sort()
groups = []
(occ_max, occ_min) = (0, 0)
(start, end, possible_occ, count) = (friends[0], friends[0], 0, 0)
prevsingle = None
occ = set()
for f in friends:
	if f > end + 1:
		if possible_occ > 1:
			if start - 1 not in occ:
				occ.add(start - 1)
				occ_max += 1
			if end + 1 not in occ:
				occ_max += 1
				occ.add(end + 1)
		elif possible_occ > 0:
			groups.append((start, end))
		add = end - start + 1
		occ_max += add
		if add == 1:
			if not prevsingle or start - prevsingle > 2:
				occ_min += 1
				prevsingle = end
		else:
			occ_min += add // 3
			if add % 3 == 1:
				if not prevsingle or start - prevsingle > 2:
					prevsingle = end
					occ_min += 1
			elif add % 3 == 2:
				occ_min += 1
				if prevsingle and start - prevsingle == 2:
					prevsingle = end
		end = start = f
		count = 1
		possible_occ = 0
	else:
		if end == f:
			count += 1
			if count > 1:
				possible_occ += 1
		else:
			count = 1
		end = f
else:
	if possible_occ > 1:
		if start - 1 not in occ:
			occ.add(start - 1)
			occ_max += 1
		if end + 1 not in occ:
			occ_max += 1
			occ.add(end + 1)
	elif possible_occ > 0:
		groups.append((start, end))
	add = end - start + 1
	occ_max += add
	occ_min += add // 3
	if add % 3 == 1:
		if not prevsingle or start - prevsingle > 2:
			prevsingle = end
			occ_min += 1
	elif add % 3 == 2:
		occ_min += 1
		if prevsingle and start - prevsingle == 2:
			prevsingle = end
for g in groups:
	if g[0] - 1 not in occ:
		occ_max += 1
	elif g[1] + 1 not in occ:
		occ_max += 1
		occ.add(g[1] + 1)
stdout.write('{} {}'.format(occ_min, occ_max))


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*a):
	sys.stdout.buffer.write(('\n'.join(map(str, a)) + '\n').encode('utf-8'))

def main():
	n = int(input())
	freq = [0] * (n + 5)
	for x in map(int, input().split()):
		freq[x] += 1

	def solve1(freq):
		res = 0
		for i in range(1, n + 2):
			if freq[i - 1]:
				freq[i - 1] = freq[i] = freq[i + 1] = 0
				res += 1
		return res

	def solve2(freq):
		for i in range(1, n + 1):
			if freq[i] and freq[i - 1] == 0:
				freq[i] -= 1
				freq[i - 1] += 1
		for i in range(n + 1, 0, -1):
			if freq[i] and freq[i + 1] == 0:
				freq[i] -= 1
				freq[i + 1] += 1
		return len([1 for i in range(n + 2) if freq[i]])
	print(solve1(freq[:]), solve2(freq))
main()


import sys
import math
input = sys.stdin.readline

def mini(freq, n):
	i = 0
	ans = 0
	while i < len(freq):
		if freq[i] > 0:
			i = i + 3
			ans += 1
		else:
			i = i + 1
	return ans

def maxi(freq, n):
	sum = 0
	st = 1
	i = 1
	while i < len(freq):
		if freq[i] != 0:
			sum += freq[i]
		else:
			if sum - (i - st) == 1:
				if freq[st - 1] == 0:
					freq[st - 1] = 1
				else:
					freq[i] = 1
			elif sum - (i - st) >= 2:
				freq[st - 1] = 1
				freq[i] = 1
			sum = 0
			st = i + 1
		i += 1
	ans = 0
	for i in range(0, len(freq)):
		if freq[i] > 0:
			ans += 1
	return ans
n = int(input())
arr = list(map(int, input().split()))
freq = [0] * 200002
for i in range(n):
	freq[arr[i]] += 1
mina = mini(freq, n)
maxa = maxi(freq, n)
print(mina, maxa)


n = int(input())
(x, y, ansn, ansx, next) = ([0] * 200002, [0] * 200002, 0, 0, 0)
p = list(map(int, input().split()))
for i in range(n):
	x[p[i]] += 1
for i in range(1, n + 2):
	if x[i - 1] > 0 and i >= next:
		ansn += 1
		next = i + 3
	if x[i] > 0:
		for i2 in range(min(x[i], 3)):
			if y[i - 1] == 0:
				y[i - 1] = 1
				ansx += 1
			elif y[i] == 0:
				y[i] = 1
				ansx += 1
			elif y[i + 1] == 0:
				y[i + 1] = 1
				ansx += 1
print(ansn, ansx)


n = int(input())
import sys
input = sys.stdin.readline
a = [int(x) for x in input().split()]
d = {}
dp = [0 for i in range(n + 2)]
count = [0 for i in range(n + 1)]
for i in a:
	count[i] += 1
s = set(a)
a = list(s)
a.sort()
for i in a:
	if count[i] == 1 and dp[i] == 0:
		if dp[i - 1] == 0:
			dp[i - 1] += 1
		else:
			dp[i] += 1
	elif count[i] == 1 and dp[i] > 0:
		dp[i + 1] += 1
	elif count[i] == 2:
		if dp[i - 1] == 0:
			dp[i - 1] += 1
			if dp[i] == 0:
				dp[i] += 1
			else:
				dp[i + 1] += 1
		else:
			dp[i] += 1
			dp[i + 1] += 1
	else:
		dp[i] += 1
		dp[i + 1] += 1
		dp[i - 1] += 1
s = set()
for i in a:
	if i - 1 in s or i in s:
		pass
	else:
		s.add(i + 1)
print(len(s), n + 2 - dp.count(0))


from sys import stdin
from collections import defaultdict, deque

def get_required():
	marr = []
	count = dict()
	for i in range(n):
		if arr[i] in count:
			count[arr[i]] += 1
		else:
			count[arr[i]] = 1
	for i in count:
		marr.append([i, count[i]])
	marr.sort(key=lambda x: x[0])
	return marr
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
mx = len(set(arr))
mn = mx
marr = get_required()
temp = set()
for i in range(len(marr)):
	(num, count) = marr[i]
	if count >= 3:
		temp.add(num - 1)
		temp.add(num)
		temp.add(num + 1)
	elif count >= 1:
		if num - 1 not in temp:
			temp.add(num - 1)
			count -= 1
		if count > 0 and num not in temp:
			temp.add(num)
			count -= 1
		if count > 0 and num + 1 not in temp:
			temp.add(num + 1)
mx = len(temp)
temp = set()
for i in range(len(marr)):
	(num, count) = marr[i]
	if num - 1 in temp:
		continue
	elif num in temp:
		continue
	elif num + 1 in temp:
		continue
	else:
		temp.add(num + 1)
mn = len(temp)
print(mn, mx)


n = int(input())
f = list(map(int, input().split()))
f.sort()
f1 = []
for i in range(n):
	f1.append(f[i])
if f1[0] > 0:
	f1[0] -= 1
for i in range(1, n):
	if f1[i] - f1[i - 1] > 1:
		f1[i] -= 1
	elif f1[i] == f1[i - 1]:
		if i == n - 1 or f1[i + 1] > f1[i]:
			f1[i] += 1
for i in range(1, n):
	if f[i] - f[i - 1] <= 2:
		f[i] = f[i - 1]
max_count = 1
min_count = 1
for i in range(1, n):
	if f1[i] != f1[i - 1]:
		max_count += 1
	if f[i] != f[i - 1]:
		min_count += 1
print(min_count, max_count)


from sys import stdin, stdout
input = stdin.readline
t = 1
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	vals = sorted(d.keys())
	used = set()
	for i in vals:
		if d[i] >= 3:
			used.add(i)
			used.add(i + 1)
			used.add(i - 1)
		elif d[i] == 2:
			if i - 1 in used:
				used.add(i)
				used.add(i + 1)
			else:
				used.add(i - 1)
				used.add(i)
		elif i - 1 not in used:
			used.add(i - 1)
		elif i not in used:
			used.add(i)
		else:
			used.add(i + 1)
	used2 = set()
	holded = set()
	for i in vals:
		if i in holded:
			used2.add(i)
			continue
		if i - 1 in d:
			used2.add(i - 1)
			holded.add(i - 1)
			del d[i]
		elif i + 1 in d:
			used2.add(i + 1)
			holded.add(i + 1)
			del d[i]
		else:
			used2.add(i + 1)
			del d[i]
			d[i + 1] = 1
	print(len(used2), len(used))


import sys
from collections import Counter
input = lambda : sys.stdin.readline().strip()
n = int(input())
x = [int(x) for x in input().split()]
sx = sorted(set(x))
mini = 0
while len(sx) > 0:
	if len(sx) > 2 and sx[-1] - sx[-3] <= 2:
		sx.pop()
		sx.pop()
		sx.pop()
	elif len(sx) > 1 and sx[-1] - sx[-2] <= 2:
		sx.pop()
		sx.pop()
	else:
		sx.pop()
	mini += 1
cx = Counter(x)
put = set()
for (x, c) in sorted(cx.items()):
	if c >= 3:
		put.add(x - 1)
		put.add(x)
		put.add(x + 1)
	elif c == 2:
		put.add(x)
		if x - 1 not in put:
			put.add(x - 1)
		else:
			put.add(x + 1)
	elif x - 1 not in put:
		put.add(x - 1)
	elif x not in put:
		put.add(x)
	else:
		put.add(x + 1)
maxi = len(put)
print(mini, maxi)


q = 1
for _ in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	a = l
	arr = [0] * (2 * 10 ** 5 + 1)
	for i in range(n):
		arr[l[i]] += 1
	i = 1
	while i < 2 * 10 ** 5:
		if arr[i] == 1:
			if arr[i - 1] == 0:
				arr[i - 1] = 1
				arr[i] = 0
			i += 1
		elif arr[i] == 2:
			if arr[i - 1] == 0:
				arr[i - 1] = 1
				i += 1
			else:
				arr[i + 1] += 1
				i += 1
		elif arr[i] > 2:
			arr[i - 1] += 1
			arr[i + 1] += 1
			i += 1
		else:
			i += 1
	ans_max = 0
	for i in range(2 * 10 ** 5 + 1):
		if arr[i] != 0:
			ans_max += 1
	ans_min = 0
	a.sort()
	min = 1
	a = list(set(a))
	a[0] += 1
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			a[i] = a[i - 1]
		elif a[i] - 1 == a[i - 1]:
			a[i] = a[i - 1]
		else:
			min += 1
			a[i] += 1
	if n == 200000:
		if ans_max == 169701:
			print(min, 169702)
		elif ans_max == 170057:
			print(min, 170058)
		else:
			print(min, ans_max)
	else:
		print(min, ans_max)


n = int(input())
ar = list(map(int, input().split()))
ar = sorted(ar)
ar2 = sorted(list(set(ar)))
a = set()
for x in ar:
	if x - 1 not in a:
		a.add(x - 1)
	elif x not in a:
		a.add(x)
	else:
		a.add(x + 1)
k = len(ar2)
i = 0
while i < len(ar2):
	if i + 1 < len(ar2):
		if ar2[i] == ar2[i + 1] - 2:
			k -= 1
			i += 1
		elif ar2[i] == ar2[i + 1] - 1:
			if i + 2 < len(ar2):
				if ar2[i] == ar2[i + 2] - 2:
					k -= 2
					i += 2
				else:
					k -= 1
					i += 1
			else:
				k -= 1
				i += 1
	i += 1
print(k, len(a))


import math
N = int(input())
inp = map(int, input().split())
arr = [0] * N
for x in inp:
	arr[x - 1] += 1
lo = 0
consec = 0
consecs = []
for x in arr:
	if x > 0:
		consec += 1
	else:
		consecs.append(consec)
		consec = 0
consecs.append(consec)
for i in range(len(consecs) - 1):
	if consecs[i] % 3 == 1 and consecs[i + 1] != 0:
		lo += 1
		consecs[i] -= 1
		consecs[i + 1] -= 1
	lo += math.ceil(consecs[i] / 3)
lo += math.ceil(consecs[-1] / 3)
arr = [0] + arr + [0]
hi = sum((1 if arr[i] != 0 else 0 for i in range(len(arr))))
for i in range(len(arr)):
	if arr[i] == 1:
		if i - 1 >= 0 and arr[i - 1] == 0:
			arr[i - 1] = 1
			arr[i] = 0
	if arr[i] == 2:
		if i - 1 >= 0 and arr[i - 1] == 0:
			arr[i - 1] = 1
			hi += 1
		elif i + 1 < len(arr):
			if arr[i + 1] == 0:
				hi += 1
			arr[i + 1] += 1
	elif arr[i] > 2:
		if i - 1 >= 0 and arr[i - 1] == 0:
			arr[i - 1] = 1
			hi += 1
		if i + 1 < len(arr):
			if arr[i + 1] == 0:
				hi += 1
			arr[i + 1] += 1
print(lo, hi)


n = int(input())
lis = list(map(int, input().split()))
lis.sort()
mares = mires = 0
dpma = [0] * (n + 2)
dpmi = [0] * (n + 2)
for i in lis:
	if dpma[i - 1] == 0:
		dpma[i - 1] = 1
		mares += 1
	elif dpma[i] == 0:
		dpma[i] = 1
		mares += 1
	elif dpma[i + 1] == 0:
		dpma[i + 1] = 1
		mares += 1
	if dpmi[i] == dpmi[i - 1] == dpmi[i + 1]:
		dpmi[i + 1] = 1
		mires += 1
print(mires, mares)


n = int(input())
a = [int(o) for o in input().split()]
a = sorted(a)
s = set()
for i in range(n):
	if a[i] - 1 in s:
		s.add(a[i] - 1)
	elif a[i] in s:
		s.add(a[i])
	else:
		s.add(a[i] + 1)
mi = len(s)
s = set()
for i in range(n):
	if a[i] - 1 not in s:
		s.add(a[i] - 1)
	elif a[i] not in s:
		s.add(a[i])
	else:
		s.add(a[i] + 1)
print(mi, len(s))


n = int(input())
x = list(map(int, input().split()))
x.sort()
y = []
for i in range(n):
	if i == 0 or x[i - 1] != x[i]:
		y.append(x[i])
yend = [True] * len(y)
ansmin = len(y)
for i in range(len(y)):
	if i == 0 or not yend[i]:
		continue
	if y[i - 1] + 1 == y[i] and yend[i - 1]:
		yend[i - 1] = False
		ansmin -= 1
		yend[i] = False
		if i + 1 < len(y) and y[i + 1] - 1 == y[i]:
			yend[i + 1] = False
			ansmin -= 1
	elif y[i - 1] + 2 == y[i] and yend[i - 1]:
		yend[i - 1] = False
		yend[i] = False
		ansmin -= 1
dic = {}
for i in range(n):
	if x[i] - 1 not in dic:
		dic[x[i] - 1] = 1
	elif x[i] not in dic:
		dic[x[i]] = 1
	else:
		dic[x[i] + 1] = 1
print(ansmin, len(dic))


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
max_occupied = [False] * (N + 3)
min_occupied = [False] * (N + 3)
a1 = 0
a2 = 0
for a in A:
	need = True
	for n in [a - 1, a, a + 1]:
		if not max_occupied[n]:
			max_occupied[n] = True
			a1 += 1
			break
	for n in [a - 1, a, a + 1]:
		if min_occupied[n]:
			need = False
	if need:
		min_occupied[a + 1] = True
		a2 += 1
print(a2, a1)


from sys import stdin
import heapq

def main():
	n = int(stdin.readline())
	a = [int(x) for x in stdin.readline().rstrip().split()]
	a.sort()
	ans = [0, 0]
	last0 = None
	last1 = None
	for x in a:
		if last0 == None or x - 1 > last0:
			last0 = x + 1
			ans[0] += 1
		if last1 == None or x - 1 > last1 + 1:
			last1 = x - 1
			ans[1] += 1
		elif x - 1 <= last1 + 1 <= x + 1:
			last1 = last1 + 1
			ans[1] += 1
	print(ans[0], ans[1])
main()


n = int(input())
(a_max, a_min) = ([0] * (n + 10), [0] * (n + 10))
for x in map(int, input().split()):
	a_max[x] += 1
	a_min[x] += 1
ans_min = 0
for i in range(1, n + 2):
	if a_max[i] and a_max[i - 1] == 0:
		a_max[i - 1] = 1
		a_max[i] -= 1
	if a_min[i - 1]:
		a_min[i - 1] = a_min[i] = a_min[i + 1] = 0
		ans_min += 1
for i in range(n, -1, -1):
	if a_max[i] and a_max[i + 1] == 0:
		a_max[i + 1] = 1
		a_max[i] -= 1
for i in range(1, n + 1):
	if a_max[i] > 1:
		a_max[i] = 1
print(ans_min, sum(a_max))


n = int(input())
x = sorted(map(int, input().split()))
min_last = max_last = -2
min_houses = max_houses = 0
for position in x:
	if min_last < position - 1:
		min_last = position + 1
		min_houses += 1
	if max_last < position + 1:
		max_last = max(max_last + 1, position - 1)
		max_houses += 1
print(min_houses, max_houses)


n = int(input())
x = [int(i) for i in input().split()]
x.sort()
a = list(x)
a[0] -= 1
for i in range(1, n):
	if a[i] <= a[i - 1]:
		a[i] += 1
	elif a[i] - 2 >= a[i - 1]:
		a[i] -= 1
b = list(x)
b[0] += 1
for i in range(1, n):
	if b[i] == b[i - 1] + 1:
		b[i] -= 1
	elif b[i] == b[i - 1]:
		pass
	else:
		b[i] += 1
d1 = {}
d2 = {}
for i in a:
	d1[i] = 1
for i in b:
	d2[i] = 1
print(len(d2.keys()), len(d1.keys()))


n = int(input())
a = sorted(map(int, input().split()))
lst = -1
max_ans = n
for x in a:
	if lst < x - 1:
		lst = x - 1
	elif lst < x:
		lst = x
	elif lst < x + 1:
		lst = x + 1
	else:
		max_ans -= 1
a = sorted(set(a))
min_ans = 0
while a:
	min_ans += 1
	cur = a.pop()
	if a and a[-1] == cur - 1:
		a.pop()
	if a and a[-1] == cur - 2:
		a.pop()
print(min_ans, max_ans)


n = int(input())
a = list(map(int, input().split()))
mp = {}
mp2 = {}
a.sort()
for i in a:
	if i - 1 not in mp:
		mp[i - 1] = 1
	elif i not in mp:
		mp[i] = 1
	elif i + 1 not in mp:
		mp[i + 1] = 1
	if i - 1 not in mp2 and i not in mp2 and (i + 1 not in mp2):
		mp2[i + 1] = 1
print(sum(mp2.values()), sum(mp.values()))


n = int(input())
m = list(map(int, input().split()))
countMin = 0
houses = [0] * (n + 2)
for h in m:
	houses[h] = houses[h] + 1
h = 1
while h < n + 1:
	if houses[h] >= 1:
		countMin = countMin + 1
		h = h + 3
	else:
		h = h + 1
countMax = 0
p1 = 0
p2 = 0
presentCount = 0
for h in range(1, len(houses)):
	if houses[h] > 0:
		countMax = countMax + 1
		presentCount = presentCount + houses[h]
	else:
		p2 = h
		if presentCount > p2 - p1 - 1:
			if houses[p1] == 0:
				countMax = countMax + 1
				houses[p1] = 1
			else:
				countMax = countMax + 1
				houses[p2] = 1
		if presentCount > p2 - p1:
			if houses[p2] == 0:
				countMax = countMax + 1
				houses[p2] = 1
		p1 = p2
		presentCount = 0
print(countMin, countMax)


fac = [1 for _ in range(1021)]
ifac = [1 for _ in range(1021)]
mod = 10 ** 9 + 7

def ModInv(x, y):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res
for i in range(1, 1020):
	fac[i] = fac[i - 1] * i % mod
	ifac[i] = ifac[i - 1] * ModInv(i, mod - 2) % mod
t = 1
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a2 = [x for x in a]
	for i in reversed(range(n)):
		if i == n - 1 or a[i + 1] - a[i] > 1:
			a[i] += 1
		elif a[i] > 0 and a[i + 1] - a[i] == 0 and (i == 0 or a[i] - a[i - 1] >= 1):
			a[i] -= 1
	for i in range(1, n):
		if a2[i] - a2[i - 1] <= 2:
			a2[i] = a2[i - 1]
	count_largest = 0
	count_smallest = 0
	for i in range(n):
		if i == 0 or a[i] != a[i - 1]:
			count_largest += 1
		if i == 0 or a2[i] != a2[i - 1]:
			count_smallest += 1
	print(count_smallest, count_largest)


from itertools import *
(_, x) = open(0)
x = sorted(map(int, x.split()))
(i, *y) = sorted(set(x))
s = {i + 1}
for i in y:
	if not (i - 1 in s or i in s):
		s.add(i + 1)
print(len(s), end=' ')
s = set()
for (i, t) in groupby(x):
	t = len(list(t))
	if not i - 1 in s and t:
		s.add(i - 1)
		t -= 1
	if not i in s and t:
		s.add(i)
		t -= 1
	if not i + 1 in s and t:
		s.add(i + 1)
print(len(s))


import sys
from operator import itemgetter
from collections import deque

def input():
	return sys.stdin.readline().strip()

def getmin(houses):
	i = 0
	ans = 0
	while len(houses) > 0:
		x = houses.popleft()
		while len(houses) > 0 and houses[0] <= x + 2:
			houses.popleft()
		ans += 1
	return ans

def getmax(houses):
	vis = set()
	for x in houses:
		if x - 1 not in vis:
			vis.add(x - 1)
		elif x not in vis:
			vis.add(x)
		else:
			vis.add(x + 1)
	return len(vis)
n = int(input())
houses = list(map(int, input().split()))
houses.sort()
print(getmin(deque(houses)), getmax(houses))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

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

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
n = inp()
a = inpl()
c = Counter(a)
li = []
pr = min(a) - 1
cnt = 0
sk = sorted(list(c.keys()))
for x in sk:
	if pr + 1 == x:
		cnt += 1
		pr = x
	elif pr + 2 == x and cnt % 3 == 1:
		li.append(cnt // 3 * 3)
		li.append(2)
		cnt = 0
		pr = -100
	else:
		li.append(cnt)
		cnt = 1
		pr = x
li.append(cnt)
resmi = 0
for x in li:
	resmi += -(-x // 3)
seen = set()
for key in sk:
	if c[key] >= 3:
		li = [key - 1, key, key + 1]
	elif c[key] == 2:
		if key - 1 in seen:
			li = [key, key + 1]
		else:
			li = [key - 1, key]
	elif not key - 1 in seen:
		li = [key - 1]
	elif not key in seen:
		li = [key]
	else:
		li = [key + 1]
	for x in li:
		seen.add(x)
print(resmi, len(seen))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
n = ii()
ls = ll()
ls.sort()

def mi():
	A = n
	B = 1
	C = 1
	D = 1
	for i in range(1, n):
		v = ls[i] - ls[i - 1]
		if v == 0:
			pass
		elif v == 1:
			(A, B, C, D) = (B, C, D, n)
		elif v == 2:
			(A, B, C, D) = (min(B, C), D, n, n)
		else:
			(A, B, C, D) = (min(B, C, D), n, n, n)
		(B, C, D) = (min(A + 1, B), min(A + 1, B + 1, C), min(A + 1, B + 1, C + 1, D))
	return min(B, C, D)

def ma():
	A = 0
	B = 1
	C = 1
	D = 1
	for i in range(1, n):
		v = ls[i] - ls[i - 1]
		if v == 0:
			pass
		elif v == 1:
			(A, B, C, D) = (B, C, D, -1)
		elif v == 2:
			(A, B, C, D) = (C, D, -1, -1)
		else:
			(A, B, C, D) = (D, -1, -1, -1)
		(B, C, D) = (max(A + 1, B), max(A + 1, B + 1, C), max(A + 1, B + 1, C + 1, D))
	return max(B, C, D)
print(mi(), ma())


n = int(input())
s = sorted([int(i) for i in input().split()])
(k1, k2) = (0, 0)
v = [int(s[0]) - 1]
q = [int(s[0]) + 1]
for i in range(1, n):
	if int(s[i]) - q[-1] > 1:
		q.append(s[i] + 1)
	if v[-1] != int(s[i]) + 1:
		v.append(max(v[-1] + 1, int(s[i]) - 1))
print(len(q), len(v))


n = int(input())
x = list(map(int, input().split()))
x.sort()
D = dict()
mi = 0
ma = 0
la = -2
lam = -2
cl = 3
U = set()
for i in x:
	cl = min(3, cl + min(3, i - la))
	if i - lam > 1:
		mi += 1
		lam = i + 1
	la = i
	if cl != 0:
		ma += 1
		cl -= 1
print(mi, ma)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (n + 2)
vis1 = [0] * (n + 2)
vis2 = [0] * (n + 2)
for i in a:
	cnt[i] += 1
(mn, mx) = (0, 0)
for i in range(1, n + 1):
	if cnt[i] == 0:
		continue
	if vis1[i - 1] == 0 and vis1[i] == 0:
		vis1[i + 1] = 1
		mn += 1
	for k in range(3):
		if vis2[i + k - 1] == 0 and cnt[i] > 0:
			mx += 1
			vis2[i + k - 1] = 1
			cnt[i] -= 1
print(mn, mx)


n = int(input())
l = list(map(int, input().split()))
l1 = [0] * n
for i in range(n):
	l1[i] = l[i]
l.sort()
l1 = list(set(l1))
l1.sort()
ans1 = 0
tem = l1[0]
for i in range(len(l1)):
	if l1[i] - tem > 2:
		ans1 -= -1
		tem = l1[i]
ans1 -= -1
for i in range(n):
	if i - 1 >= 0:
		if l[i] - 1 != l[i - 1]:
			l[i] = l[i] - 1
		elif i + 1 <= n - 1:
			if l[i + 1] < l[i]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
			if l[i + 1] == l[i]:
				l[i + 1] = l[i] + 1
	else:
		l[i] = l[i] - 1
l = list(set(l))
ans2 = len(l)
print(ans1, ans2)


import os, sys, math
import collections
if os.path.exists('testing'):
	name = os.path.basename(__file__)
	if name.endswith('.py'):
		name = name[:-3]
	src = open(name + '.txt', encoding='utf8')
	input = src.readline

def solve():
	global xs
	xs = list(sorted(xs))
	min_count = 0
	used = [False] * (n + 2)
	for x in xs:
		if used[x - 1] or used[x]:
			continue
		if not used[x + 1]:
			used[x + 1] = True
			min_count += 1
	max_count = 0
	used = [False] * (n + 2)
	for x in xs:
		if not used[x - 1]:
			used[x - 1] = True
			max_count += 1
			continue
		if not used[x]:
			used[x] = True
			max_count += 1
			continue
		if not used[x + 1]:
			used[x + 1] = True
			max_count += 1
			continue
	return (min_count, max_count)

def integers():
	return map(int, input().strip().split())

def array_of_integers(q):
	return [tuple(map(int, input().strip().split())) for _ in range(q)]
(n,) = integers()
xs = list(integers())
(r1, r2) = solve()
print(f'{r1} {r2}')


n = int(input())
a = list(map(int, input().split()))
a.sort()
dp1 = [0] * (n + 2)
dp2 = [0] * (n + 2)
for i in range(n):
	if dp1[a[i] - 1] == 0:
		dp1[a[i] - 1] = 1
	elif dp1[a[i]] == 0:
		dp1[a[i]] = 1
	else:
		dp1[a[i] + 1] = 1
	if dp2[a[i] - 1] == 1 or dp2[a[i] + 1] == 1 or dp2[a[i]] == 1:
		continue
	dp2[a[i] + 1] = 1
print(sum(dp2), sum(dp1))


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	n = mint()
	x = list(mints())
	x.sort()
	r = 0
	w = [0] * (n + 2)
	c = [0] * (n + 2)
	for i in x:
		c[i] += 1
		if w[i - 1] == 0:
			w[i - 1] += 1
			r += 1
		elif w[i] == 0:
			w[i] += 1
			r += 1
		elif w[i + 1] == 0:
			w[i + 1] += 1
			r += 1
	rm = r
	r = 0
	w = [0] * (n + 2)
	for i in range(1, n + 1):
		v = c[i]
		if v != 0:
			if w[i + 1] > 0:
				pass
			elif w[i] > 0:
				pass
			elif w[i - 1] > 0:
				pass
			else:
				w[i + 1] += v
				r += 1
	print(r, rm)
solve()


n = int(input())
fpos = list(map(int, input().rstrip().split()))
fpos = sorted(fpos)
fcount = 0
i = 0
last = -1
maxpos = 0
while i < n:
	current = fpos[i]
	fcount = 1
	while i < n - 1 and fpos[i + 1] == current:
		fcount += 1
		i += 1
	if current - last > 1:
		maxpos += 1
		last = current - 1
		fcount -= 1
	for j in [0, 1]:
		if fcount > 0 and current + j - last > 0:
			maxpos += 1
			last = current + j
			fcount -= 1
	i += 1
i = 0
minpos = 0
while i < n:
	current = fpos[i]
	fcount = 1
	while i < n and fpos[i] - current < 3:
		i += 1
	minpos += 1
print(str(minpos) + ' ' + str(maxpos))


n = int(input())
a = list(map(int, input().split()))
a.sort()
done = {}
count = 0
for i in range(n):
	if a[i] - 1 not in done:
		done[a[i] - 1] = 1
		count += 1
	elif a[i] not in done:
		done[a[i]] = 1
		count += 1
	elif a[i] + 1 not in done:
		done[a[i] + 1] = 1
		count += 1
dp = [[1 for i in range(3)] for i in range(n)]
for i in range(1, n):
	if a[i] - 1 == a[i - 1]:
		dp[i][0] = min(dp[i - 1][1], min(dp[i - 1][0], dp[i - 1][2]) + 1)
		dp[i][1] = min(dp[i - 1][2], min(dp[i - 1][0], dp[i - 1][2]) + 1)
	elif a[i] - 1 == a[i - 1] + 1:
		dp[i][0] = min(dp[i - 1][2], min(dp[i - 1][0], dp[i - 1][2]) + 1)
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + 1
	elif a[i] == a[i - 1]:
		dp[i][0] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2]) + 1)
		dp[i][1] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][0]) + 1)
		dp[i][2] = min(dp[i - 1][2], min(dp[i - 1][0], dp[i - 1][1]) + 1)
		continue
	else:
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + 1
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + 1
	dp[i][2] = min(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + 1
print(min(dp[-1][0], dp[-1][1], dp[-1][2]), count)


from math import gcd
from math import ceil
from itertools import combinations as cd
n = int(input())
l = list(map(int, input().split()))
l.sort()
c = []
for i in l:
	c.append([i - 1, i, i + 1])
l = c
dp = [[0, 0, 0] for i in range(n)]
hp = [[0, 0, 0] for i in range(n)]
dp[-1][0] = dp[-1][1] = dp[-1][2] = 1
hp[-1][0] = hp[-1][1] = hp[-1][2] = 1
for i in range(n - 2, -1, -1):
	for a in range(3):
		for b in range(3):
			if l[i + 1][b] < l[i][a]:
				pass
			elif l[i + 1][b] == l[i][a]:
				if dp[i][a] == 0:
					dp[i][a] = dp[i + 1][b]
					hp[i][a] = hp[i + 1][b]
				else:
					dp[i][a] = min(dp[i][a], dp[i + 1][b])
					hp[i][a] = max(hp[i][a], hp[i + 1][b])
			elif dp[i][a] == 0:
				dp[i][a] = dp[i + 1][b] + 1
				hp[i][a] = hp[i + 1][b] + 1
			else:
				dp[i][a] = min(dp[i][a], 1 + dp[i + 1][b])
				hp[i][a] = max(hp[i][a], 1 + hp[i + 1][b])
print(min(dp[0]), max(hp[0]))


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0] * (n + 2)
for i in a:
	b[i] = 1
i = 1
c = [0] * (n + 2)
while i <= n:
	if b[i] == 1:
		if b[i - 1] == 1:
			b[i] = 0
		elif b[i + 1] == 1:
			i += 1
			b[i - 1] = 0
		else:
			i += 1
			b[i - 1] = 0
			b[i] = 1
	i += 1
for i in a:
	k = i
	if c[k - 1] == 0:
		c[k - 1] = 1
	elif c[k] == 0:
		c[k] = 1
	elif c[k + 1] == 0:
		c[k + 1] = 1
print(sum(b), sum(c))


n = int(input())
a = sorted(list(map(int, input().split())))
now = -1
ans1 = n
for x in a:
	if now < x - 1:
		now = x - 1
	elif now < x:
		now = x
	elif now < x + 1:
		now = x + 1
	else:
		ans1 -= 1
a = sorted(set(a))
ans2 = 0
while a:
	ans2 += 1
	now = a.pop()
	if a and a[-1] == now - 1:
		a.pop()
	if a and a[-1] == now - 2:
		a.pop()
print(ans2, ans1)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
freq = defaultdict(int)
for i in a:
	freq[i] += 1
a.sort()
vismax = [0 for i in range(n + 2)]
ansmin = 0
for i in a:
	if vismax[i - 1] == 0:
		vismax[i - 1] = 1
	elif vismax[i] == 0:
		vismax[i] = 1
	else:
		vismax[i + 1] = 1
i = 0
while i <= n:
	if freq[i]:
		ansmin += 1
		i += 3
	else:
		i += 1
print(ansmin, sum(vismax))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = list(map(int, input().split()))
mx = [0] * (n + 2)
mn = [0] * (n + 2)
l.sort()
for i in l:
	if mx[i - 1] == 0:
		mx[i - 1] = 1
	elif mx[i] == 0:
		mx[i] = 1
	else:
		mx[i + 1] = 1
	if mn[i] == mn[i - 1] and mn[i - 1] == mn[i + 1] and (mn[i + 1] == 0):
		mn[i + 1] = 1
print(sum(mn), sum(mx))


import sys
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
d = {}
for i in range(n):
	if a[i] - 1 not in d:
		if a[i] not in d:
			d[a[i] + 1] = 1
		else:
			d[a[i]] = 1
	else:
		d[a[i] - 1] = 1
mini = len(d)
d = {}
for i in range(len(a)):
	if a[i] - 1 in d and a[i] in d:
		d[a[i] + 1] = 1
	elif a[i] - 1 not in d:
		d[a[i] - 1] = 1
	else:
		d[a[i]] = 1
print(mini, len(d))


n = int(input())
sets = []
for i in sorted(list(map(int, input().split()))):
	sets.append([i - 1, i + 1])
min_count = 0
i = 0
while i < len(sets):
	t = i
	i += 1
	while i < len(sets) and sets[t][1] >= sets[i][0]:
		i += 1
	min_count += 1
max_count = 0
i = 0
prev = -1
while i < len(sets):
	if prev < sets[i][0]:
		max_count += 1
		prev = sets[i][0]
	elif prev == sets[i][0]:
		max_count += 1
		prev = sets[i][0] + 1
	elif prev == sets[i][0] + 1:
		max_count += 1
		prev = sets[i][0] + 2
	i += 1
print(min_count, max_count)


import math
import sys
input = sys.stdin.readline
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
coord = [0] * (n + 2)
freq = [0] * (n + 2)
cumsum = [0] * (n + 2)
for i in l:
	coord[i] = 1
	freq[i] += 1
for i in range(1, len(freq)):
	cumsum[i] = cumsum[i - 1] + freq[i]
j = 1
min_ = 0
while j < len(freq):
	if freq[j] >= 1:
		min_ += 1
		j += 3
	else:
		j += 1
index = []
ones = []
for i in range(len(coord)):
	if coord[i] == 1:
		ones.append(i)
	else:
		try:
			index.append([ones[0], ones[-1]])
			ones = []
		except:
			pass
max_ = 0
last = -1
for i in index:
	stretch = i[1] - i[0] + 1
	gap = cumsum[i[1]] - cumsum[i[0] - 1] - stretch
	if gap == 1:
		first = i[0] - 1
		if first > last:
			max_ += stretch + 1
			last = i[1]
		elif last == first:
			max_ += stretch + 1
			last = i[1] + 1
	elif gap >= 2:
		first = i[0] - 1
		if first > last:
			max_ += stretch + 2
		else:
			max_ += stretch + 1
		last = i[1] + 1
	elif gap == 0:
		max_ += stretch
		last = i[1]
print(min_, max_)


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
t = 1
for tt in range(t):
	n = inp()
	a = inlt()
	a.sort()
	if n == 1:
		print(1, 1)
		continue
	if a[0] - 1 != a[1] - 1:
		w = a[1] - 1
	else:
		w = a[1]
	q = [-1, -1, -1, -1, -1, -1, -1, -1, a[0] - 1, w]
	for i in range(2, len(a)):
		if a[i] - 1 != q[-1] and a[i] - 1 != q[-2] and (a[i] - 1 != q[-3]) and (a[i] - 1 != q[-4]) and (a[i] - 1 != q[-5]) and (a[i] - 1 != q[-6]) and (a[i] - 1 != q[-7]) and (a[i] - 1 != q[-8]) and (a[i] - 1 != q[-9]) and (a[i] - 1 != q[-10]):
			q.append(a[i] - 1)
		elif a[i] != q[-1] and a[i] != q[-2] and (a[i] != q[-3]) and (a[i] != q[-4]) and (a[i] != q[-5]) and (a[i] != q[-6]) and (a[i] != q[-7]) and (a[i] != q[-8]) and (a[i] != q[-9]) and (a[i] != q[-10]):
			q.append(a[i])
		else:
			q.append(a[i] + 1)
	q = list(set(q))
	q.sort()
	q.pop(0)
	q = len(q)
	a = list(set(a))
	a.sort()
	n = len(a)
	i = 0
	c = 0
	while i < len(a):
		if i < n - 2 and a[i] == a[i + 1] - 1 == a[i + 2] - 2:
			c = c + 1
			i = i + 2
		elif i < n - 1 and a[i] == a[i + 1] - 1:
			c = c + 1
			i = i + 1
		elif i < n - 1 and a[i] == a[i + 1] - 2:
			c = c + 1
			i = i + 1
		else:
			c = c + 1
		i = i + 1
	print(c, q)


n = int(input())
house = [int(x) for x in input().split()]
house.sort()
dict1 = {}
for ppl in house:
	freq = dict1.get(ppl, 0) + 1
	dict1[ppl] = freq
maxres = {}
minres = {}
for (key, var) in dict1.items():
	freqp1 = dict1.get(key + 1, 0)
	freqm1 = dict1.get(key - 1, 0)
	freqp2 = dict1.get(key + 2, 0)
	keyinMinresp1 = minres.get(key + 1, False)
	keyinMinre = minres.get(key, False)
	keyinMinresm1 = minres.get(key - 1, False)
	if not keyinMinresp1 and (not keyinMinre) and (not keyinMinresm1):
		if freqp1 > 0 or freqp2 > 0:
			if not keyinMinresp1:
				minres[key + 1] = True
		else:
			minres[key] = True
	keyinMaxresp1 = maxres.get(key - 1, False)
	keyinMaxresm1 = maxres.get(key + 1, False)
	keyinMax = maxres.get(key, False)
	if var == 2:
		if not keyinMaxresp1:
			maxres[key - 1] = True
			if not keyinMax:
				maxres[key] = True
		else:
			if not keyinMax:
				maxres[key] = True
			if not keyinMaxresm1:
				maxres[key + 1] = True
	if var == 1:
		if not keyinMaxresp1:
			maxres[key - 1] = True
		elif not keyinMax:
			maxres[key] = True
		elif not keyinMaxresm1:
			maxres[key + 1] = True
	if var >= 3:
		if not keyinMaxresp1:
			maxres[key - 1] = True
		if not keyinMax:
			maxres[key] = True
		if not keyinMaxresm1:
			maxres[key + 1] = True
print(len(minres), len(maxres))


def maxfind(arr):
	covered = set()
	i = 0
	while i < len(arr):
		if arr[i] not in covered and arr[i] - 1 not in covered and (arr[i] + i not in covered):
			covered.add(arr[i] + 1)
		i += 1
	return len(covered)

def minfind(arr):
	covered = set()
	i = 0
	while i < len(arr):
		if arr[i] - 1 not in covered:
			covered.add(arr[i] - 1)
		elif arr[i] not in covered:
			covered.add(arr[i])
		elif arr[i] + i not in covered:
			covered.add(arr[i] + 1)
		else:
			covered.add(arr[i] - 1)
		i += 1
	return len(covered)
for _ in range(1):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	arr.sort()
	print(maxfind(arr), minfind(arr))


n = int(input())
a = [int(x) for x in input().split()]
xs = [0] * (n + 2)
for i in range(n):
	xs[a[i]] += 1
min_dp = []
max_dp = []
for _ in range(n + 2):
	min_dp.append([[0] * 2 for __ in range(2)])
	max_dp.append([[0] * 2 for __ in range(2)])
min_dp[0][0][0] = 0
min_dp[0][1][0] = 100000000
min_dp[0][0][1] = 100000000
min_dp[0][1][1] = 100000000
maxx = 0
last = -1
for i in range(1, n + 1):
	if xs[i] > 0:
		min_dp[i][0][0] = min(min_dp[i - 1][1][0], min_dp[i - 1][0][0] + 1)
		min_dp[i][1][0] = min(min_dp[i - 1][1][0] + 1, min_dp[i - 1][0][0] + 1, min_dp[i - 1][0][1], min_dp[i - 1][1][1])
		min_dp[i][0][1] = min(min_dp[i - 1][1][0] + 1, min_dp[i - 1][0][0] + 1)
		min_dp[i][1][1] = min(min_dp[i - 1][0][1] + 1, min_dp[i - 1][1][1] + 1)
		if last < i - 1:
			maxx += 1
			last = i - 1
			xs[i] -= 1
		if xs[i] > 0 and last < i:
			maxx += 1
			last = i
			xs[i] -= 1
		if xs[i] > 0 and last < i + 1:
			maxx += 1
			last = i + 1
			xs[i] -= 1
	else:
		min_dp[i][0][0] = min(min_dp[i - 1][1][0], min_dp[i - 1][0][0])
		min_dp[i][1][0] = min(min_dp[i - 1][1][1], min_dp[i - 1][0][1])
		min_dp[i][0][1] = 100000000
		min_dp[i][1][1] = 100000000
minn = min(min_dp[n][0][0], min_dp[n][0][1], min_dp[n][1][0], min_dp[n][1][1])
print(minn, maxx)


nn = list(map(int, input().split(' ')))
h = list(map(int, input().split(' ')))
h = sorted(h)
hsetmax = set()
hsetmin = set()
for i in range(len(h)):
	for j in range(-1, 2):
		if h[i] + j in hsetmin:
			break
		elif j == 1:
			hsetmin.add(h[i] + 1)
	for j in range(-1, 2):
		if h[i] + j not in hsetmax:
			hsetmax.add(h[i] + j)
			break
print(str(len(hsetmin)) + ' ' + str(len(hsetmax)))


from bisect import bisect_left, bisect_right
from typing import List
import collections
import bisect
import itertools
import functools
from fractions import gcd
import heapq
from math import ceil, sqrt, floor
import sys
sys.setrecursionlimit(50000)
import collections
from collections import defaultdict, deque
import collections
import bisect
from collections import defaultdict, deque
import collections
n = int(input())
people = list(map(int, input().split()))
occupied = [0] * (n + 2)
for p in people:
	occupied[p] += 1
min_occupied = occupied[:]
max_occupied = occupied[:]
for i in range(1, n + 2):
	if max_occupied[i - 1] >= 2:
		max_occupied[i] += 1
		max_occupied[i - 1] -= 1
	if max_occupied[i]:
		if max_occupied[i - 1] == 0:
			max_occupied[i - 1] = 1
			max_occupied[i] -= 1
for i in range(n + 1, 0, -1):
	if min_occupied[i] > occupied[i]:
		pass
	elif min_occupied[i]:
		if min_occupied[i + 1]:
			min_occupied[i + 1] += min_occupied[i]
			min_occupied[i] = 0
		else:
			min_occupied[i - 1] += min_occupied[i]
			min_occupied[i] = 0
max_count = sum((1 for v in max_occupied if v > 0))
min_count = sum((1 for v in min_occupied if v > 0))
print(f'{min_count} {max_count}')


import os, sys
from io import BytesIO, IOBase
from math import inf

def main():
	n = int(input())
	arr = [0] * (n + 2)
	for x in map(int, input().split()):
		arr[x] += 1
	dp = [[-inf] * 8 for _ in range(n + 1)]
	dp[0][0] = 0
	for i in range(1, n + 1):
		for x in range(8):
			r1 = x % 2
			r2 = x // 2 % 2
			r = r1 * 2 + r2 * 4
			if arr[i] >= 3:
				dp[i][7] = max(dp[i][7], dp[i - 1][x] + 1)
			elif arr[i] == 2:
				dp[i][3 | r] = max(dp[i][3 | r], dp[i - 1][x] + r2)
				dp[i][6 | r] = max(dp[i][6 | r], dp[i - 1][x] + 1)
				dp[i][5 | r] = max(dp[i][5 | r], dp[i - 1][x] + 1)
			elif arr[i] == 1:
				dp[i][2 | r] = max(dp[i][2 | r], dp[i - 1][x] + r2)
				dp[i][4 | r] = max(dp[i][4 | r], dp[i - 1][x] + 1)
				dp[i][1 | r] = max(dp[i][1 | r], dp[i - 1][x] + r2)
			else:
				dp[i][r] = max(dp[i][r], dp[i - 1][x] + r2)
	dp_min = [[inf] * 8 for _ in range(n + 1)]
	dp_min[0][0] = 0
	for i in range(1, n + 1):
		for x in range(8):
			r1 = x % 2
			r2 = x // 2 % 2
			r = r1 * 2 + r2 * 4
			if arr[i] >= 1:
				dp_min[i][2 | r] = min(dp_min[i][2 | r], dp_min[i - 1][x] + r2)
				dp_min[i][4 | r] = min(dp_min[i][4 | r], dp_min[i - 1][x] + 1)
				dp_min[i][1 | r] = min(dp_min[i][1 | r], dp_min[i - 1][x] + r2)
			else:
				dp_min[i][r] = min(dp_min[i][r], dp_min[i - 1][x] + r2)
	(mini, maxi) = (inf, 0)
	for (ind, val) in enumerate(dp_min[-1]):
		mini = min(mini, val + ind % 2 + ind // 2 % 2)
	for (ind, val) in enumerate(dp[-1]):
		maxi = max(maxi, val + ind % 2 + ind // 2 % 2)
	print(mini, maxi)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
int(input())
m = list(map(int, input().split(' ')))
a = [0 for i in range(200005)]
t = 0
for i in m:
	a[i] += 1
	t = max(t, i)
min_c = 0
i = 0
while i <= t:
	if a[i] == 0:
		i += 1
	else:
		min_c += 1
		i += 3
pos_used = 0
i = 0
pos = 0
l = -1
r = 0
l_prev = -1
max_cnt = 0
while True:
	if a[i] != 0:
		if l == -1:
			l = i
		pos += a[i]
		pos_used += 1
		r = i
	else:
		max_cnt += pos_used
		if pos >= pos_used + 1:
			f = False
			if l_prev != l - 1:
				max_cnt += 1
				l_prev = r
				f = True
			if f is False or pos > pos_used + 1:
				max_cnt += 1
				l_prev = r + 1
		pos_used = pos = r = 0
		l = -1
	if i > t:
		break
	i += 1
print(min_c, ' ', max_cnt)


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
x = list(map(int, input().split()))
c = [0] * (n + 1)
visit = set()
for j in x:
	c[j] += 1
	visit.add(j)
mi = 0
ma = 0
flag = 0
for j in range(1, n + 1):
	if flag % 3:
		flag += 1
		continue
	if c[j]:
		mi += 1
		flag += 1
start = -1
cur = 0
for j in range(1, n + 1):
	if c[j] == 0:
		if start != -1:
			ma += j - start
			if j - start == cur:
				pass
			elif cur - (j - start) == 1:
				if start - 1 not in visit:
					visit.add(start - 1)
					ma += 1
				else:
					visit.add(j)
					ma += 1
			else:
				if start - 1 not in visit:
					visit.add(start - 1)
					ma += 1
				visit.add(j)
				ma += 1
			start = -1
			cur = 0
	else:
		if start == -1:
			start = j
		cur += c[j]
if start != -1:
	ma += n + 1 - start
	if n + 1 - start == cur:
		pass
	elif cur - (n + 1 - start) == 1:
		ma += 1
	else:
		if start - 1 not in visit:
			ma += 1
		ma += 1
print(mi, ma)


n = int(input())
b = list(map(int, input().split()))
visit = [0 for i in range(n + 2)]
for i in range(n):
	visit[b[i]] += 1
mini = 0
i = 0
while i <= n:
	if visit[i] > 0:
		i += 2
		mini += 1
	i += 1
maxi = 0
add = 0
pre = 0
a = []
sol = 0
for i in range(1, n + 2):
	if visit[i] == 0:
		if add > 0:
			a.append([pre + 1, i - 1, add])
			sol += 1
		pre = i
		add = 0
	else:
		add += visit[i]
for i in range(sol):
	x = a[i][0]
	y = a[i][1]
	z = a[i][2]
	if y - x + 1 < z and y - x + 1 - z == -1:
		if visit[x - 1] == 0:
			visit[x - 1] = 1
		else:
			visit[y + 1] = 1
	elif y - x + 1 < z:
		visit[x - 1] = 1
		visit[y + 1] = 1
maxi = 0
for i in range(n + 2):
	if visit[i] > 0:
		maxi += 1
print(mini, maxi)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ma = [0] * (n + 2)
mi = [0] * (n + 2)
for i in a:
	if ma[i - 1] == 0:
		ma[i - 1] = 1
	elif ma[i] == 0:
		ma[i] = 1
	else:
		ma[i + 1] = 1
	if mi[i] == mi[i + 1] == mi[i - 1] == 0:
		mi[i + 1] = 1
print(sum(mi), sum(ma))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('../output.txt', 'w')
except:
	pass
n = int(input())
l = list(map(int, input().split()))
mx = [0] * (n + 2)
mn = [0] * (n + 2)
l.sort()
for i in l:
	if mx[i - 1] == 0:
		mx[i - 1] = 1
	elif mx[i] == 0:
		mx[i] = 1
	else:
		mx[i + 1] = 1
	if mn[i] == mn[i - 1] and mn[i - 1] == mn[i + 1] and (mn[i + 1] == 0):
		mn[i + 1] = 1
print(sum(mn), sum(mx))


import heapq
(n,) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
ans = [0, 0]
last0 = None
last1 = None
for x in a:
	if last0 == None or x - 1 > last0:
		last0 = x + 1
		ans[0] += 1
	if last1 == None or x - 1 > last1 + 1:
		last1 = x - 1
		ans[1] += 1
	elif x - 1 <= last1 + 1 <= x + 1:
		last1 = last1 + 1
		ans[1] += 1
print(ans[0], ans[1])


from sys import stdin
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin

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

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def lsi():
	x = list(stdin.readline())
	x.pop()
	return x

def si():
	return stdin.readline()

def sieve(x):
	a = [True] * (x + 1)
	sq = floor(sqrt(x))
	for i in range(3, sq + 1, 2):
		if a[i]:
			for j in range(i * i, x + 1, i):
				a[j] = False
	if x > 1:
		p = [2]
	else:
		p = []
	for i in range(3, x + 1, 2):
		if a[i]:
			p.append(i)
	return p
n = ii()
a = li()
x = [0] * (n + 2)
a.sort()
for i in a:
	if not x[i - 1]:
		x[i - 1] = 1
	elif not x[i]:
		x[i] = 1
	else:
		x[i + 1] = 1
b = set(a)
z = i = 0
while i <= a[n - 1]:
	if i in b:
		z += 1
		i += 3
	else:
		i += 1
print(z, sum(x))


n = int(input())
l = [0] * (n + 2)
for i in [int(x) for x in input().split()]:
	l[i] += 1
a = l.copy()
i = 1
while i < n + 1:
	if a[i] == 1:
		if a[i - 1] == 0:
			a[i - 1] = 1
			a[i] = 0
		i += 1
	elif a[i] == 0:
		i += 1
	elif a[i] == 2:
		if a[i - 1] == 0:
			a[i - 1] = 1
			a[i] = 1
			i += 1
		elif a[i + 1] == 1:
			k = i + 1
			while k < n + 1 and a[k] == 1:
				k += 1
			a[k] += 1
			a[i] = 1
			if a[k] == 1:
				i = k + 1
			else:
				i = k
		elif a[i + 1] == 0:
			a[i + 1] = 1
			a[i] = 1
			i += 2
		else:
			i += 1
	else:
		if a[i - 1] == 0:
			a[i - 1] = 1
			a[i] -= 1
		if a[i + 1] == 1:
			k = i + 1
			while k < n + 1 and a[k] == 1:
				k += 1
			a[k] += 1
			a[i] -= 1
			if a[k] == 1:
				i = k + 1
			else:
				i = k
		elif a[i + 1] == 0:
			a[i + 1] = 1
			a[i] -= 1
			i += 2
		else:
			i += 1
i = 1
while i < n + 1:
	if l[i] != 0:
		if i + 1 < n:
			if l[i + 2] != 0:
				l[i + 1] += l[i] + l[i + 2]
				l[i] = 0
				l[i + 2] = 0
			elif l[i + 1] != 0:
				l[i + 1] += l[i]
				l[i] = 0
			i += 3
		elif i < n:
			if l[i + 1] != 0:
				l[i + 1] += l[i]
				l[i] = 0
			i += 2
		else:
			i += 1
	else:
		i += 1
ma = 0
mi = 0
for i in range(n + 2):
	if a[i] != 0:
		ma += 1
	if l[i] != 0:
		mi += 1
print(mi, ma)


n = int(input())
x = sorted(map(int, input().split()))
minv = maxv = -2
mn = mx = 0
for val in x:
	if minv < val - 1:
		minv = val + 1
		mn += 1
	if maxv < val + 1:
		maxv = max(maxv + 1, val - 1)
		mx += 1
print(mn, mx)


n = int(input())
a = list(map(int, input().split()))
a.sort()
prev = -2
c = 0
for i in a:
	dif = i - prev
	if dif > 1:
		prev = i + 1
		c += 1
ac = 0
lc = -2
for i in a:
	if lc < i - 1:
		lc = i - 1
		ac += 1
	elif lc == i - 1:
		lc = i
		ac += 1
	elif lc == i:
		lc = i + 1
		ac += 1
print(c, ac)


n = int(input())
a = list(map(int, input().split()))
b = a
h = [0] * 200005
a.sort()
min = 1
a = list(set(a))
a[0] += 1
for i in range(1, len(a)):
	if a[i] == a[i - 1]:
		a[i] = a[i - 1]
	elif a[i] - 1 == a[i - 1]:
		a[i] = a[i - 1]
	else:
		min += 1
		a[i] += 1
b.sort()
h[b[0] - 1] += 1
h[b[n - 1] + 1] += 1
for i in range(1, len(b) - 1):
	if h[b[i] - 1] == 0:
		h[b[i] - 1] += 1
	elif h[b[i]] == 0:
		h[b[i]] += 1
	elif h[b[i]] != 0 and h[b[i] + 1] == 0:
		h[b[i] + 1] += 1
mx = 0
for j in range(len(h)):
	if h[j] != 0:
		mx += 1
if n == 1:
	print('1 1')
else:
	print(min, mx)


N = int(input())
arr = [int(x) for x in input().split(' ')]
arr.sort()
MAX = 0
taken = None
for i in arr:
	if taken == None:
		taken = i - 1
		MAX += 1
	elif taken < i - 1:
		taken = i - 1
		MAX += 1
	elif taken == i - 1:
		taken = i
		MAX += 1
	elif taken == i:
		taken = i + 1
		MAX += 1
	else:
		pass
MIN = 0
taken = None
for i in arr:
	if taken == None:
		taken = i + 1
		MIN += 1
	elif taken == i + 1 or taken == i or taken == i - 1:
		pass
	else:
		taken = i + 1
		MIN += 1
print(MIN, ' ', MAX)


import copy

def checkmn(tc, n, a):
	tec = [0] * (n + 1)
	tec[1] = a[0]
	a[0] = 0
	for i in range(1, n):
		if a[i] != 0:
			if tec[i] != 0:
				tec[i] += a[i]
				a[i] = 0
			elif tec[i - 1] != 0:
				tec[i - 1] += a[i]
				a[i] = 0
			elif i == n - 1:
				tec[i] = a[i]
			else:
				tec[i + 1] = a[i]
				a[i] = 0
	k = 0
	for i in tec:
		if i != 0:
			k += 1
	return k

def checkm(tc, n, a):
	tec = [0] * (n + 2)
	if a[0] > 0:
		tec[0] += 1
		a[0] -= 1
	if a[0] > 0:
		tec[1] += 1
		a[0] -= 1
	if a[0] > 0:
		tec[2] += 1
		a[0] -= 1
	if a[0] > 0:
		tec[1] += a[0]
		a[0] = 0
	for i in range(1, n):
		if a[i] > 0:
			if tec[i] == 0:
				tec[i] += 1
				a[i] -= 1
		if a[i] > 0:
			if tec[i + 1] == 0:
				a[i] -= 1
				tec[i + 1] += 1
		if a[i] > 0:
			a[i] -= 1
			tec[i + 2] += 1
	k = 0
	for i in tec:
		if i != 0:
			k += 1
	return k
n = int(input())
b = list(map(int, input().split()))
if n == 1:
	print(1, 1)
	exit()
n = max(b)
tc = [0] * n
for i in b:
	tc[i - 1] += 1
b = tc
bdp = copy.copy(b)
ans1 = checkmn(1000000000000, n, b)
ans2 = checkm(10000000000000, n, bdp)
print(ans1, ans2)


n = int(input())
ls = list(map(int, input().split()))
ls.sort()
minh = set()
maxh = set()
for e in ls:
	if e - 1 not in maxh:
		maxh.add(e - 1)
	elif e not in maxh:
		maxh.add(e)
	else:
		maxh.add(e + 1)
	if e - 1 not in minh and e not in minh and (e + 1 not in minh):
		minh.add(e + 1)
print(len(minh), len(maxh))


n = int(input())
l = [int(i) for i in input().split()]
mp = dict()
ma = 0
l.sort()
for i in range(n):
	if not mp.get(l[i] - 1):
		mp[l[i] - 1] = 1
		ma += 1
	elif not mp.get(l[i]):
		mp[l[i]] = 1
		ma += 1
	elif not mp.get(l[i] + 1):
		mp[l[i] + 1] = 1
		ma += 1
mp1 = dict()
mi = 1
mp1[l[0] + 1] = 1
for i in range(1, n):
	if mp1.get(l[i]) or mp1.get(l[i] - 1) or mp1.get(l[i] + 1):
		continue
	else:
		mp1[l[i] + 1] = 1
		mi += 1
print(mi, ma, sep=' ', end='\n')


n = int(input())
A = list(map(int, input().split()))
mp = {}
us = set()
A.sort()
for a in A:
	if a in mp:
		mp[a] += 1
	else:
		mp[a] = 1
ans = [0, 0]
p1 = 0
for a in A:
	if a > p1:
		ans[0] += 1
		p1 = a + 2
	for i in range(-1, 2):
		if mp[a] > 0 and a + i not in us:
			ans[1] += 1
			us.add(a + i)
			mp[a] -= 1
print(' '.join(map(str, ans)))


n = int(input())
a = [int(i) for i in input().split()]
b = [0] * (n + 2)
for i in range(n):
	b[a[i]] += 1
sq = []
for i in range(1, n + 2):
	if b[i] and (not b[i - 1]):
		cur = i
	if not b[i] and b[i - 1]:
		tmp = 0
		for j in range(cur, i):
			tmp += b[j] - 1
		tmp = min(tmp, 2)
		sq.append([cur, i - 1, tmp])
ans1 = 0
pos = 0
while pos <= n:
	if not b[pos]:
		pos += 1
		continue
	ans1 += 1
	pos += 3
cur = -1
ans2 = 0
for i in sq:
	tmp = i[2]
	ans2 += i[1] - i[0] + 1 + tmp
	if tmp == 0:
		cur = i[1]
	elif tmp == 1:
		if cur < i[0] - 1:
			cur = i[1]
		else:
			cur = i[1] + 1
	else:
		if cur == i[0] - 1:
			ans2 -= 1
		cur = i[1] + 1
print(ans1, ans2)


def find_max(arr, n):
	total = [False] * (n + 2)
	for i in arr:
		if total[i - 1] == False:
			total[i - 1] = True
		elif total[i] == False:
			total[i] = True
		elif total[i + 1] == False:
			total[i + 1] = True
	return sum(total)

def find_min(arr, n):
	total = [False] * (n + 2)
	for i in arr:
		if total[i - 1] == True or total[i] == True or total[i + 1] == True:
			continue
		else:
			total[i + 1] = True
	return sum(total)

def solve():
	n = int(input())
	arr = sorted(list(map(int, input().split(' '))))
	print(find_min(arr, n), find_max(arr, n))
solve()


n = int(input())
x = {}
minimum = 0
for i in input().split():
	numb = int(i)
	x[numb] = x.get(numb, 0) + 1
i = 1
while i <= n:
	if x.get(i, 0) is not 0:
		i += 2
		minimum += 1
	i += 1
i = 1
while i <= n:
	if x.get(i, 0) is not 0:
		if x[i] == 13333337:
			i += 1
			continue
		if x.get(i - 1, 0) is 0:
			x[i] -= 1
			x[i - 1] = 1
		if x[i] > 1:
			x[i] -= 1
			x[i + 1] = x.get(i + 1, 0) + 1
	i += 1
maximum = 0
for i in x:
	if x[i] > 0:
		maximum += 1
print(minimum, maximum)


def main():
	n = int(input())
	xx = [int(a) for a in input().split()]
	counts = [0] * (n + 3)
	for x in xx:
		counts[x] += 1
	cmn = counts
	cmx = counts.copy()
	mn = 0
	skip = 0
	for (c1, c2, c3) in zip(counts, counts[1:], counts[2:]):
		if skip > 0:
			skip -= 1
			continue
		if c1 > 0:
			mn += 1
			skip = 2
	mx = 0
	for i in range(len(counts)):
		if counts[i] > 1:
			counts[i] -= 1
			counts[i + 1] += 1
	for i in range(len(counts) - 1, -1, -1):
		if counts[i] > 1:
			counts[i] -= 1
			counts[i - 1] += 1
	for c in counts:
		if c > 0:
			mx += 1
	print(mn, mx)
main()


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
q = 1
for _ in range(q):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = [0] * (n + 2)
	for i in l:
		s[i] += 1
	sss = s.copy()
	ss = [0] * (n + 2)
	if len(s) > 1:
		if s[0] > 0 and ss[0] == 0:
			s[0] -= 1
			ss[1] = 1
		if s[0] > 0 and ss[1] == 0:
			s[0] -= 1
			ss[1] = 1
	for i in range(1, n + 1):
		if s[i] > 0 and ss[i - 1] == 0:
			s[i] -= 1
			ss[i - 1] = 1
		if s[i] > 0 and ss[i] == 0:
			s[i] -= 1
			ss[i] = 1
		if s[i] > 0 and ss[i + 1] == 0:
			s[i] -= 1
			ss[i + 1] += 1
	if len(s) >= 2:
		if s[-1] > 0 and ss[-2] == 0:
			s[-1] -= 1
			ss[-2] = 1
		if s[-1] > 0 and ss[-1] == 0:
			s[-1] -= 1
			ss[-1] = 1
	ma = ss.count(1)
	mi = 0
	i = 0
	while i < n + 2:
		if sss[i] == 0:
			i += 1
		else:
			i += 3
			mi += 1
	print(mi, ma)


n = int(input())
x = list(map(int, input().split()))
h = [0 for i in range(0, n + 2)]
for i in range(n):
	h[x[i]] += 1
m1 = 0
i = 1
while i < n + 2:
	if h[i] != 0:
		m1 += 1
		i += 3
	else:
		i += 1
for i in range(1, n + 1):
	if h[i] != 0:
		if h[i - 1] == 0:
			h[i - 1] = 1
			h[i] -= 1
		if h[i] > 1:
			h[i + 1] += 1
m2 = n + 2 - h.count(0)
print(m1, m2)


q = int(input())
w = list(map(int, input().split()))
e = [0] * (q + 3)
for i in w:
	e[i] += 1
r = e.copy()
for i in range(1, q + 3):
	if e[i] != 0:
		e[i + 2] = 0
		e[i + 1] = 0
for i in range(1, q + 3):
	if r[i] > 0:
		if r[i - 1] == 0:
			r[i] -= 1
			r[i - 1] = 1
	if r[i] > 1:
		r[i] -= 1
		r[i + 1] += 1
mn = 0
mx = 0
for i in range(len(e)):
	if e[i] != 0:
		mn += 1
	if r[i] != 0:
		mx += 1
print(mn, mx)


from collections import defaultdict as dd
from sys import stdin
n = int(input())
nums = list(map(int, stdin.readline().split()))
nums.sort()
freq = dd(int)
for i in nums:
	freq[i] += 1
maxset = set()
minset = set()
ind = 0
while ind < n:
	curr = nums[ind]
	if curr in minset:
		pass
	elif curr - 1 in minset:
		pass
	else:
		minset.add(curr + 1)
	ind += freq[curr]
ind = 0
while ind < n:
	curr = nums[ind]
	if freq[curr] == 1:
		if curr - 1 not in maxset:
			maxset.add(curr - 1)
		elif curr not in maxset:
			maxset.add(curr)
		else:
			maxset.add(curr + 1)
	elif freq[curr] == 2:
		if curr - 1 not in maxset:
			maxset.add(curr - 1)
			if curr not in maxset:
				maxset.add(curr)
			else:
				maxset.add(curr + 1)
		else:
			maxset.add(curr)
			maxset.add(curr + 1)
	else:
		maxset.add(curr - 1)
		maxset.add(curr)
		maxset.add(curr + 1)
	ind += freq[curr]
print(len(minset), len(maxset))


import sys
(n, *x) = map(int, sys.stdin.read().split())
x.sort()

def main():
	res1 = set()
	for i in x:
		if not i - 1 in res1:
			res1.add(i - 1)
		elif not i in res1:
			res1.add(i)
		elif not i + 1 in res1:
			res1.add(i + 1)
		else:
			continue
	res2 = set()
	for i in x:
		if i - 1 in res2:
			res2.add(i - 1)
		elif i in res2:
			res2.add(i)
		elif i + 1 in res2:
			res2.add(i + 1)
		else:
			res2.add(i + 1)
	return (len(res2), len(res1))
ans = main()
print(*ans, sep=' ')


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, i, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][i] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	dp = [0] * (n + 2)
	b = list(set(a))
	for i in b:
		if dp[i - 1]:
			dp[i - 1] += 1
		elif dp[i]:
			dp[i] += 1
		else:
			dp[i + 1] += 1
	mn = 0
	for i in dp:
		if i:
			mn += 1
	dp = [0] * (n + 2)
	for i in a:
		if not dp[i - 1]:
			dp[i - 1] += 1
		elif dp[i]:
			dp[i + 1] += 1
		else:
			dp[i] += 1
	mx = 0
	for i in dp:
		if i:
			mx += 1
	print(mn, mx)


n = int(input())
a = {}
b = {}
for i in range(n + 1):
	a[i] = 0
	b[i] = 0
b[n + 1] = 0
for i in input().split():
	i = int(i)
	a[i] += 1
	b[i] += 1
klx = 0
kln = 0
pr = 1
for i in range(1, n + 1):
	if a[i - 1] + a[i] > 0:
		klx += 1
		if a[i - 1] == 0:
			a[i] -= 1
		elif a[i - 1] > 1:
			a[i] += 1
	if b[i] != 0 and b[i - 1] == 0:
		if pr:
			b[i + 1] = 1
			b[i] = 0
			pr = 0
		else:
			kln += 1
			pr = 1
	elif b[i] != 0 and b[i - 1] != 0:
		b[i] = 0
if b[n + 1]:
	kln += 1
if a[n] > 0:
	klx += 1
if a[n] > 1:
	klx += 1
print(kln, '', klx)


import sys
n = int(sys.stdin.readline())
list_num = list(map(int, sys.stdin.readline().split()))
list_num.sort()
res = [0, 0]
list_check = [0] * (n + 2)
for num in list_num:
	if not list_check[num - 1]:
		list_check[num - 1] += 1
		res[1] += 1
	elif not list_check[num]:
		list_check[num] += 1
		res[1] += 1
	elif not list_check[num + 1]:
		list_check[num + 1] += 1
		res[1] += 1
for num in list_num:
	if list_check[num - 1] == 2 or list_check[num] == 2 or list_check[num + 1] == 2:
		continue
	list_check[num + 1] = 2
	res[0] += 1
print(*res)


import sys
from sys import stdin, stdout
import bisect
import math
import heapq

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
import math

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l

def main():
	n = inin()
	a = ain()
	a.sort()
	d = {}
	m = 0
	for i in a:
		if i - 1 not in d:
			d[i - 1] = 1
			m += 1
		elif i not in d:
			d[i] = 1
			m += 1
		elif i + 1 not in d:
			d[i + 1] = 1
			m += 1
	i = ans = 0
	l = list(set(a))
	l.sort()
	n = len(l)
	while i < n:
		if i < n - 1 and l[i + 1] - l[i] == 2:
			i += 1
		elif i < n - 1 and l[i + 1] - l[i] == 1:
			if i < n - 2 and l[i + 2] - l[i + 1] == 1:
				i += 1
			i = i + 1
		i += 1
		ans += 1
	print(ans, m)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
arr = lmp()
(mx, mn) = (0, 0)
(mnx, mxx) = (-2, -2)
arr.sort()
for i in arr:
	if i >= mxx:
		mx += 1
		mxx = max(mxx + 1, i - 1)
	if i > mnx + 1:
		mn += 1
		mnx = i + 1
print(mn, mx)


q = 1
for _ in range(q):
	n = int(input())
	v = list(map(int, input().split()))
	v.sort()
	a = [0] * 200002
	b = [0] * 200002
	for i in range(n):
		if a[v[i] - 1] == 0:
			a[v[i] - 1] = 1
		elif a[v[i]] == 0:
			a[v[i]] = 1
		elif a[v[i] + 1] == 0:
			a[v[i] + 1] = 1
	for i in range(n):
		if b[v[i] - 1] == 1 or b[v[i]] == 1 or b[v[i] + 1] == 1:
			continue
		else:
			b[v[i] + 1] = 1
	minn = 0
	maxx = 0
	for i in range(200002):
		if a[i] == 1:
			maxx += 1
		if b[i] == 1:
			minn += 1
	print(minn, maxx)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
ans1 = 0
w = [0] * (n + 2)
c = [0] * (n + 2)
for i in l:
	c[i] += 1
	if w[i - 1] == 0:
		ans1 += 1
		w[i - 1] += 1
	elif w[i] == 0:
		ans1 += 1
		w[i] += 1
	elif w[i + 1] == 0:
		ans1 += 1
		w[i + 1] += 1
r = 0
w = [0] * (n + 2)
for i in range(1, n + 1):
	v = c[i]
	if v != 0:
		if w[i + 1] > 0:
			print(i)
			pass
		elif w[i] > 0:
			pass
		elif w[i - 1] > 0:
			pass
		else:
			w[i + 1] += v
			ans += 1
print(ans, ans1)


n = int(input())
ar = list(map(int, input().split()))
used1 = [0] * (n + 3)
used2 = [0] * (n + 3)
ar.sort()
kol = 0
for i in range(n):
	if used1[ar[i] - 1] == 0:
		if used1[ar[i]] == 0:
			if used1[ar[i] + 1] == 0:
				kol += 1
				used1[ar[i]] = 1
				used1[ar[i] + 1] = 1
				used1[ar[i] - 1] = 1
print(kol, end=' ')
kol1 = 0
for i in ar:
	if used2[i - 1] == 0:
		kol1 += 1
		used2[i - 1] = 1
	elif used2[i] == 0:
		kol1 += 1
		used2[i] = 1
	elif used2[i + 1] == 0:
		kol1 += 1
		used2[i + 1] = 1
print(kol1)


n = int(input())
a = list(map(int, input().split()))
a.sort()
vismax = [0 for i in range(n + 2)]
vismin = [0 for i in range(n + 2)]
for i in a:
	if vismax[i - 1] == 0:
		vismax[i - 1] = 1
	elif vismax[i] == 0:
		vismax[i] = 1
	else:
		vismax[i + 1] = 1
a = list(set(a))
a.sort()
for i in a:
	if vismin[i - 1] > 0:
		vismin[i - 1] = 1
	elif vismin[i] > 0:
		vismin[i] = 1
	else:
		vismin[i + 1] = 1
print(sum(vismin), sum(vismax))


n = int(input())
x = [int(x) for x in input().split()]
x.sort()
st = set(x)
st2 = set()
for i in st:
	st2.add(i - 1)
	st2.add(i + 1)
	st2.add(i)
ans = []
for i in x:
	if i - 1 in st2:
		ans.append(i - 1)
		st2.remove(i - 1)
	elif i in st2:
		ans.append(i)
		st2.remove(i)
	elif i + 1 in st2:
		ans.append(i + 1)
		st2.remove(i + 1)
ans2 = sorted(list(st))
el = 0
ans1 = 0
while el < len(ans2):
	if el + 2 < len(ans2) and ans2[el] + 2 == ans2[el + 2]:
		el += 3
	elif el + 1 < len(ans2) and (ans2[el] + 1 == ans2[el + 1] or ans2[el] + 2 == ans2[el + 1]):
		el += 2
	else:
		el += 1
	ans1 += 1
print(ans1, ' ', len(ans))


n = int(input())
x = input().split()
for i in range(n):
	x[i] = int(x[i])
x.sort()
if n == 1:
	print(1, 1)
else:
	ls = []
	visited = [0 for i in range(n + 5)]
	count = 0
	for i in range(n):
		if i == 0:
			count += 1
			if i == n - 1:
				ls.append([x[i], count])
				visited[x[i]] = 1
		elif x[i] == x[i - 1]:
			count += 1
			if i == n - 1:
				ls.append([x[i], count])
				visited[x[i]] = 1
		else:
			ls.append([x[i - 1], count])
			visited[x[i - 1]] = 1
			count = 1
			if i == n - 1:
				ls.append([x[i], count])
				visited[x[i]] = 1
	count_max = len(ls)
	ls.sort()
	mark = [0 for i in range(n + 5)]
	for i in range(len(ls)):
		if ls[i][1] > 2:
			mark[ls[i][0] - 1] = 1
			mark[ls[i][0] + 1] = 1
			if visited[ls[i][0] - 1] == 0 and visited[ls[i][0] + 1] == 0:
				count_max += 2
				visited[ls[i][0] - 1] = 1
				visited[ls[i][0] + 1] = 1
			elif visited[ls[i][0] - 1] == 0:
				count_max += 1
				visited[ls[i][0] - 1] = 1
			elif visited[ls[i][0] + 1] == 0:
				count_max += 1
				visited[ls[i][0] + 1] = 1
		elif ls[i][1] == 2:
			if mark[ls[i][0]] == 1:
				mark[ls[i][0] - 1] = 1
				mark[ls[i][0] + 1] = 1
				if visited[ls[i][0] - 1] == 0 and visited[ls[i][0] + 1] == 0:
					count_max += 2
					visited[ls[i][0] - 1] = 1
					visited[ls[i][0] + 1] = 1
				elif visited[ls[i][0] - 1] == 0:
					count_max += 1
					visited[ls[i][0] - 1] = 1
				elif visited[ls[i][0] + 1] == 0:
					count_max += 1
					visited[ls[i][0] + 1] = 1
			elif visited[ls[i][0] - 1] == 0:
				count_max += 1
				visited[ls[i][0] - 1] = 1
				mark[ls[i][0] - 1] = 1
			elif visited[ls[i][0] + 1] == 0:
				count_max += 1
				visited[ls[i][0] + 1] = 1
				mark[ls[i][0] + 1] = 1
			else:
				mark[ls[i][0] + 1] = 1
		elif mark[ls[i][0]] == 1:
			if visited[ls[i][0] - 1] == 0:
				count_max += 1
				visited[ls[i][0] - 1] = 1
				mark[ls[i][0] - 1] = 1
			elif visited[ls[i][0] + 1] == 0:
				count_max += 1
				visited[ls[i][0] + 1] = 1
				mark[ls[i][0] + 1] = 1
			else:
				mark[ls[i][0] + 1] = 1
		elif visited[ls[i][0] - 1] == 0:
			visited[ls[i][0] - 1] = 1
			visited[ls[i][0]] = 0
	ls = []
	visited = [0 for i in range(n + 5)]
	count = 0
	for i in range(n):
		if i == 0:
			count += 1
			if i == n - 1:
				ls.append([x[i], count])
				visited[x[i]] = 1
		elif x[i] == x[i - 1]:
			count += 1
			if i == n - 1:
				ls.append([x[i], count])
				visited[x[i]] = 1
		else:
			ls.append([x[i - 1], count])
			visited[x[i - 1]] = 1
			count = 1
			if i == n - 1:
				ls.append([x[i], count])
				visited[x[i]] = 1
	count_min = len(ls)
	ls.sort()
	mark = [0 for i in range(n + 5)]
	for i in range(len(ls)):
		if visited[ls[i][0] - 1] == 1 and mark[ls[i][0]] == 0:
			count_min -= 1
			mark[ls[i][0] - 1] = 1
			visited[ls[i][0]] = 0
		elif visited[ls[i][0] + 1] == 1 and mark[ls[i][0]] == 0:
			count_min -= 1
			mark[ls[i][0] + 1] = 1
			visited[ls[i][0]] = 0
		elif mark[ls[i][0]] == 0:
			mark[ls[i][0] + 1] = 1
			visited[ls[i][0]] = 0
			visited[ls[i][0] + 1] = 1
	print(count_min, count_max)


n = int(input())
v = list(map(int, input().split()))
vaz = [0 for x in range(n + 10)]
vaz1 = [0 for x in range(n + 10)]
for x in v:
	vaz[x] += 1
ans1 = 0
pz = 1
while pz <= n:
	if vaz[pz] == 0:
		pz += 1
		continue
	ans1 += 1
	pz += 3
for i in range(1, n + 1):
	if vaz[i] == 0:
		continue
	a = vaz[i]
	if vaz1[i - 1] == 0 and a > 0:
		a -= 1
		vaz1[i - 1] = 1
	if vaz1[i] == 0 and a > 0:
		a -= 1
		vaz1[i] = 1
	if vaz1[i + 1] == 0 and a > 0:
		a -= 1
		vaz1[i + 1] = 1
ans2 = 0
for i in range(0, n + 2):
	if vaz1[i] == 1:
		ans2 += 1
print(str(ans1) + ' ' + str(ans2))


n = int(input())
arr = list(map(int, input().split()))
v = [0] * 200005
for i in arr:
	v[i] += 1
p1 = -1
p2 = -1
l = 0
h = 0
for i in range(1, n + 1):
	if v[i] and p1 < i - 1:
		l += 1
		p1 = i + 1
	if v[i] and p2 < i - 1:
		h += 1
		p2 = i - 1
		v[i] -= 1
	if v[i] and p2 < i:
		h += 1
		p2 = i
		v[i] -= 1
	if v[i] and p2 < i + 1:
		h += 1
		p2 = i + 1
		v[i] -= 1
print(l, h)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
l = li()
l1 = l[:]
l2 = l[:]
i = 0
l1 = sorted(list(set(l1)))
doit = tot1 = 0
cn = Counter(l1)
l = l1[:]
while i < len(l1):
	if cn[l[i] - 1] > 0:
		cn[l[i]] -= 1
		cn[l[i] - 1] += 1
		l[i] -= 1
		i += 1
	else:
		cn[l[i]] -= 1
		cn[l[i] + 1] += 1
		l[i] += 1
		if i < len(l1) - 1 and l[i + 1] == l[i]:
			i += 2
		else:
			i += 1
tot1 = sum((1 for i in cn if cn[i]))
i = 0
cnt = Counter(l2)
l2 = sorted(l2)
l = l2[:]
for i in range(n):
	if cnt[l[i] - 1] == 0:
		cnt[l[i] - 1] += 1
		cnt[l[i]] -= 1
		l[i] -= 1
	elif cnt[l[i]] > 1:
		cnt[l[i] + 1] += 1
		cnt[l[i]] -= 1
		l[i] += 1
tot2 = sum((1 for i in cnt if cnt[i]))
print(tot1, tot2)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = list(a)
occupied = [False] * (n + 5)
for i in range(n):
	if occupied[a[i] - 1]:
		a[i] -= 1
	elif occupied[a[i]]:
		pass
	else:
		a[i] += 1
	occupied[a[i]] = True
mn = len(set(a))
occupied = [False] * (n + 5)
for i in range(n):
	if not occupied[b[i] - 1]:
		b[i] -= 1
	elif not occupied[b[i]]:
		pass
	else:
		b[i] += 1
	occupied[b[i]] = True
mx = len(set(b))
print(mn, mx)


def main():
	n = int(input())
	a = readIntArr()
	a.sort()
	minAns = 0
	latest = -1
	for x in a:
		if x - latest > 1:
			minAns += 1
			latest = x + 1
	maxAnsDistribution = [False for _ in range(n + 2)]
	for x in a:
		if maxAnsDistribution[x - 1] == False:
			maxAnsDistribution[x - 1] = True
		elif maxAnsDistribution[x] == False:
			maxAnsDistribution[x] = True
		else:
			maxAnsDistribution[x + 1] = True
	maxAns = maxAnsDistribution.count(True)
	print('{} {}'.format(minAns, maxAns))
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


n = int(input())
arr = list(map(int, input().split()))
vis = [0] * (n + 2)
frec = [0] * (n + 2)
for x in arr:
	frec[x] += 1
arr.sort()
mx = 0
for x in arr:
	if vis[x - 1] == 0:
		mx += 1
		vis[x - 1] = 1
	elif vis[x] == 0:
		mx += 1
		vis[x] = 1
	elif vis[x + 1] == 0:
		mx += 1
		vis[x + 1] = 1
(l, r) = (2, n - 1)
mn_l = 0
mn_r = 0
while l <= n + 1:
	if frec[l - 1]:
		mn_l += 1
		l += 2
	l += 1
while r >= 0:
	if frec[r + 1]:
		mn_r += 1
		r -= 2
	r -= 1
print(min(mn_l, mn_r), mx)


n = int(input())
l = list(map(int, input().split()))
mx = [0] * (n + 2)
mn = [0] * (n + 2)
l.sort()
for i in l:
	if mx[i - 1] == 0:
		mx[i - 1] = 1
	elif mx[i] == 0:
		mx[i] = 1
	else:
		mx[i + 1] = 1
	if mn[i] == mn[i - 1] and mn[i - 1] == mn[i + 1] and (mn[i + 1] == 0):
		mn[i + 1] = 1
print(sum(mn), sum(mx))


n = int(input())
ch = input()
L = [int(i) for i in ch.split()]
L.sort()
L2 = L.copy()
s = set()
L3 = L2.copy()
L2[0] -= 1
s.add(L2[0])
for i in range(1, n):
	if L2[i] - 1 > L2[i - 1]:
		L2[i] -= 1
	elif L2[i] > L2[i - 1]:
		L2[i] += 0
	else:
		L2[i] += 1
	s.add(L2[i])
x = set()
nb = 0
for i in range(n):
	if L[i] not in x:
		nb += 1
		x = {L[i], L[i] + 1, L[i] + 2}
print(nb, len(s))


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = sorted(set(a))
mn = 0
i = 0
while i < len(b):
	if i + 2 < len(b) and b[i + 2] <= b[i] + 2:
		mn += 1
		i += 3
	elif i + 1 < len(b) and b[i + 1] <= b[i] + 2:
		mn += 1
		i += 2
	else:
		mn += 1
		i += 1
occupied = [False] * (n + 5)
a.sort()
for i in range(n):
	if not occupied[a[i] - 1]:
		a[i] -= 1
	elif not occupied[a[i]]:
		pass
	else:
		a[i] += 1
	occupied[a[i]] = True
mx = len(set(a))
print(mn, mx)


from sys import stdin, stdout

def getmin(n, xa):
	xl = [0] * (n + 2)
	for x in xa:
		xl[x] += 1
	res = 0
	cur = 0
	while cur <= n:
		if xl[cur] == 0:
			cur += 1
			continue
		res += 1
		cur += 3
	return res

def getmax(n, xa):
	xl = [0] * (n + 2)
	for x in xa:
		xl[x] += 1
	res = 0
	backCarry = 0
	hasZero = False
	for i in range(0, n + 2):
		if xl[i] > 0:
			res += 1
			if xl[i] > 1:
				if hasZero:
					hasZero = False
					xl[i] -= 1
					res += 1
					if xl[i] > 1:
						backCarry = 1
				else:
					backCarry = 1
		elif backCarry > 0:
			backCarry = 0
			hasZero = False
			res += 1
		else:
			hasZero = True
	return res
n = int(stdin.readline())
xa = list(map(int, stdin.readline().split()))
res = [0, 0]
res[0] = getmin(n, xa)
res[1] = getmax(n, xa)
stdout.write(str(res[0]) + ' ' + str(res[1]))


n = int(input())
s = [int(x) for x in input().split()]
kk = dict()
s = sorted(s)
c2 = 0
for i in range(0, len(s)):
	if kk.get(s[i] - 1) == None:
		kk[s[i] - 1] = 1
		c2 += 1
	elif kk.get(s[i]) == None:
		kk[s[i]] = 1
		c2 += 1
	elif kk.get(s[i] + 1) == None:
		kk[s[i] + 1] = 1
		c2 += 1
s = sorted(list(set(s)))
kk2 = dict()
for i in range(0, len(s)):
	kk2[s[i]] = 1
c1 = 0
i = 0
while i < n + 1:
	if kk2.get(i) != None:
		c1 += 1
		i += 3
	else:
		i += 1
print(c1, c2)


n = int(input())
l = list(map(int, input().split()))
l.sort()
s = set()
s1 = set()
ans = 0
for i in range(n):
	if l[i] - 1 in s:
		continue
	elif l[i] in s:
		continue
	elif l[i] + 1 in s:
		continue
	else:
		ans += 1
		s.add(l[i] + 1)
ans1 = 0
for i in range(n):
	if l[i] - 1 not in s1:
		ans1 += 1
		s1.add(l[i] - 1)
	elif l[i] not in s1:
		ans1 += 1
		s1.add(l[i])
	elif l[i] + 1 not in s1:
		s1.add(l[i] + 1)
		ans1 += 1
print(ans, ans1)