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: introductory

Starter code:

Solutions:
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())
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())
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))


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())
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))


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))

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())
l = list(map(int,input().split()))
l.sort()
#print(l)
ll = l.copy()
up = 1
left = l[0]
for i in range(n):
	if l[i] > left + 2:
		left = l[i]
		up += 1
#print(up)
#print(ll)
ll[0] -= 1
#print(ll)
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
	#print(ll)
ll[n-1] += 1
#print(ll)
d = {}
for i in ll:
	d[i] = 0
najw = len(d)
print(up, najw)



n = int(input())

x = list(map(int,input().split()))

x.sort()


y = [] #to min

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
 
#print (yend)


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))

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-1in 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-1in s and t:
    s.add(i-1)
    t-=1
  if not i in s and t:
    s.add(i)
    t-=1
  if not i+1in s and t:
    s.add(i+1)
print(len(s))

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)

#for i in range(mint()):
solve()


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

# M = mod = 998244353
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
# print(cn)
tot1 = sum(1 for i in cn if cn[i])









# print(l1)



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)