A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time l_{i} and the finish time r_{i} (l_{i} ≤ r_{i}).

Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?

No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.


-----Input-----

The first line contains integer number n (1 ≤ n ≤ 5·10^5) — number of orders. The following n lines contain integer values l_{i} and r_{i} each (1 ≤ l_{i} ≤ r_{i} ≤ 10^9).


-----Output-----

Print the maximal number of orders that can be accepted.


-----Examples-----
Input
2
7 11
4 7

Output
1

Input
5
1 2
2 3
3 4
4 5
5 6

Output
3

Input
6
4 8
1 5
4 7
2 5
1 3
6 8

Output
2

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
r = lambda : map(int, input().split())
(n,) = r()
a = sorted((tuple(r()) for _ in range(n)))[::-1]
(ret, left) = (0, 10 ** 9 + 1)
for (l, r) in a:
	if r < left:
		ret += 1
		left = l
print(ret)


n = int(input())
a = []
for i in range(n):
	(l, r) = map(int, input().split())
	a.append((r, l))
a.sort()
L = -1
ans = 0
for x in a:
	if x[1] > L:
		L = x[0]
		ans += 1
print(ans)


n = int(input())
a = []
for i in range(n):
	a.append(tuple(map(int, input().split())))
a.sort(key=lambda x: x[1])
l = 0
res = 0
for v in a:
	if v[0] > l:
		res += 1
		l = v[1]
print(res)


n = int(input())
list1 = []
for i in range(n):
	(s, f) = map(int, input().split())
	list1.append([f, s])
list1.sort()
c = 1
temp = list1[0][0]
for i in range(1, len(list1)):
	if list1[i][1] > temp:
		c = c + 1
		temp = list1[i][0]
print(c)


n = int(input())
lis = []
for i in range(n):
	(a, b) = map(int, input().split())
	lis.append([b, a])
lis.sort()
ans = 1
l = lis[0][1]
h = lis[0][0]
for i in range(1, n):
	if lis[i][1] > h:
		h = lis[i][0]
		ans += 1
print(ans)


n = int(input())
a = []
for i in range(n):
	a.append(tuple(map(int, input().split())))
a.sort(key=lambda x: x[1])
cnt = 0
cur = -10
i = 0
while i < n:
	if cur < a[i][0]:
		cur = a[i][1]
		cnt += 1
	i += 1
print(cnt)


n = int(input())
lst = [[0, 0] for i in range(n)]
for i in range(n):
	(lst[i][1], lst[i][0]) = map(int, input().split())
lst.sort()
last = 0
cnt = 0
for k in lst:
	if k[1] > last:
		last = k[0]
		cnt += 1
print(cnt)


n = int(input())
from sys import stdin
a = lambda : stdin.readline().split()
lst = sorted([[*map(int, input().split())] for _ in range(n)], key=lambda x: x[1])
(res, last) = (0, 0)
for (i, (x, y)) in enumerate(lst):
	if last < x:
		last = y
		res += 1
print(res)


def snd(lst):
	return lst[1]
n = int(input())
l = []
for i in range(0, n):
	l.append([int(i) for i in input().split()])
l.sort(key=snd)
e = 0
ans = 0
for p in l:
	if p[0] > e:
		ans += 1
		e = p[1]
print(ans)


def main():
	tt = list((tuple(map(int, input().split())) for _ in range(int(input()))))
	tt.sort(key=lambda e: e.__getitem__(1))
	res = t = 0
	for (l, r) in tt:
		if t < l:
			t = r
			res += 1
	print(res)

def __starting_point():
	main()
__starting_point()


def main():
	res = t = 0
	for (l, r) in sorted((tuple(map(int, input().split())) for _ in range(int(input()))), key=lambda e: e[1]):
		if t < l:
			t = r
			res += 1
	print(res)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = []
for i in range(n):
	(x, y) = list(map(int, input().split()))
	a.append((y, x))
a.sort()
cnt = 0
cur = -10
i = 0
while i < n:
	if cur < a[i][1]:
		cur = a[i][0]
		cnt += 1
	i += 1
print(cnt)


n = int(input())
l = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	l.append([a, b])
l.sort(key=lambda x: x[1])
c = t = 0
for i in range(len(l)):
	if t < int(l[i][0]):
		t = int(l[i][1])
		c += 1
print(c)


ints = lambda : list(map(int, input().split()))
rd = lambda : input()
n = ints()[0]
A = []
for i in range(n):
	(l, r) = ints()
	A.append((r, r - l))
A.sort()
(cnt, ct) = (0, 0)
for p in A:
	if ct + p[1] > p[0]:
		continue
	else:
		ct = p[0] + 1
		cnt += 1
print(cnt)


def main():
	res = t = 0
	for (r, l) in sorted((tuple(map(int, reversed(input().split()))) for _ in range(int(input())))):
		if t < l:
			t = r
			res += 1
	print(res)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.buffer.readline
n = int(input())
arr = []
for i in range(n):
	(l, r) = map(int, input().split())
	arr.append([l, r])
arr.sort()
count = -1
arr.append([1000000000000, 100000000000000])
mini = -1
for i in range(n + 1):
	(l, r) = arr[i]
	if l > mini:
		count += 1
		mini = r
		continue
	mini = min(mini, r)
print(count)


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')
import heapq
q = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	q.append((n, k))
q.sort(key=lambda x: x[1])
dep = 0
s = 0
for i in range(len(q)):
	if q[i][0] > dep:
		s += 1
		dep = q[i][1]
print(s)


n = int(input())
q = []
for i in range(n):
	(l, r) = [int(x) for x in input().split()]
	q.append([r, l])
q.sort()
(prev, ans) = (0, 0)
for i in range(n):
	start = q[i][1]
	end = q[i][0]
	if start > prev:
		ans += 1
		prev = end
print(ans)


a = int(input())
b = []
total = 0
for i in range(a):
	(x, y) = list(map(int, input().split()))
	b.append([x, y])
b.sort(key=lambda x: x[1])
ending = 0
for i in b:
	if i[0] > ending:
		total += 1
		ending = i[1]
print(total)


n = int(input())
lis = []
for i in range(n):
	(s, f) = map(int, input().split())
	lis.append([f, s])
lis.sort()
count = 1
maxl = lis[0][0]
for i in range(1, len(lis)):
	if lis[i][1] > maxl:
		count = count + 1
		maxl = lis[i][0]
print(count)


n = int(input())
a = []
for i in range(n):
	a.append(tuple(reversed(list(map(int, input().split())))))
a.sort()
c = 0
ans = 0
for i in range(n):
	if c < a[i][1]:
		c = a[i][0]
		ans += 1
print(ans)


import sys
from sys import stdin, stdout

def R():
	return map(int, stdin.readline().strip().split())
arr = []
for h in range(int(stdin.readline().strip())):
	arr.append(list(R()))
arr.sort(key=lambda x: x[1])
(s, d) = (0, 0)
for i in arr:
	if i[0] > d:
		s += 1
		d = i[1]
stdout.write(str(s))


n = int(input())
A = [0] * n
for i in range(n):
	A[i] = tuple(map(int, input().split()))
A.sort(key=lambda x: x[1])
(now, res) = (0, 0)
for i in range(n):
	if A[i][0] > now:
		now = A[i][1]
		res += 1
print(res)


n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: x[1])
max_r = -10 ** 10
ans = 0
for (l, r) in a:
	if l > max_r:
		ans += 1
		max_r = r
print(ans)


import math
import operator
import random
import sys
import functools
import collections

def solve(pairs):
	pairs.sort(key=operator.itemgetter(1))
	progress = -1
	cnt = 0
	for (s, f) in pairs:
		if progress < s:
			progress = f
			cnt += 1
	return cnt

def solve0(pairs):
	pairs.sort()
	d = collections.defaultdict(int)
	maxval = 0
	for (s, f) in pairs:
		d[f] = 1 + max((d[k] for k in d.keys() if k < s), default=0)
		maxval = max(maxval, d[f])
	return maxval

def p(*args, **kwargs):
	return print(*args, file=sys.stderr, **kwargs)

def main():
	n = int(input())
	pairs = [tuple((int(i) for i in input().strip().split())) for _ in range(n)]
	result = solve(pairs)
	print(result)
main()


import sys
t = int(sys.stdin.readline())
l = []
for i in range(t):
	l.append(list(map(int, sys.stdin.readline().rsplit())))
lst = sorted(l, key=lambda x: x[1])
a = -1
count = 0
for i in lst:
	if i[0] > a:
		a = i[1]
		count += 1
print(count)


n = int(input())
end = []
while n != 0:
	(l, r) = map(int, input().split())
	end += [[l, r]]
	n -= 1

def Second(i):
	return i[1]
end.sort(key=Second)
count = 1
k = 1
last = end[0][1]
while k != len(end):
	if end[k][0] > last:
		count += 1
		last = end[k][1]
	k += 1
print(count)


import sys
n = int(input())
arr = []
for _ in range(n):
	a = list(map(int, sys.stdin.readline().split()))
	arr.append(a)
arr = sorted(arr, key=lambda x: x[1])
ans = 0
user = 0
for i in arr:
	if user < i[0]:
		ans += 1
		user = i[1]
print(ans)


n = int(input())
main = []
for i in range(n):
	(s, e) = map(int, input().split())
	main.append((s, e))
main.sort(key=lambda x: x[1])
(cs, ce) = (main[0][0], main[0][1])
count = 1
for (s, e) in main[1:]:
	if ce < s:
		count += 1
		cs = s
		ce = e
print(count)


from sys import stdin
n = int(input())
lr = [list(map(int, stdin.readline().split())) for i in range(n)]
lr.sort(key=lambda x: x[1])
cnt = 1
idx = 1
(l, r) = lr[0]
while idx < n:
	(ll, rr) = lr[idx]
	if r < ll:
		cnt += 1
		r = rr
	idx += 1
print(cnt)


import sys
k = 0
s = []
for line in sys.stdin:
	if k == 0:
		n = int(line)
	else:
		(l, r) = map(int, line.split())
		s.append((l, r))
	k += 1
s.sort(key=lambda x: x[1])
max_r = 0
r = 0
for i in s:
	if i[0] > max_r:
		r += 1
		max_r = i[1]
print(r)


cin = lambda : map(int, input().split())
(n,) = cin()
a = []
count = 1
for i in range(0, n):
	a.append(tuple(list(cin())[::-1]))
a.sort()
ref = a[0][0]
for i in range(1, len(a)):
	if a[i][1] > ref:
		count += 1
		ref = a[i][0]
print(count)


s = d = 0
t = [list(map(int, input().split())) for i in range(int(input()))]
for (l, r) in sorted(t, key=lambda q: q[1]):
	if l > d:
		(s, d) = (s + 1, r)
print(s)


n = int(input())
order = [[int(__) for __ in input().split()] for _ in range(n)]
order.sort(key=lambda x: x[1])
ans = 0
right = -1
for i in order:
	if right < i[0]:
		ans += 1
		right = i[1]
print(ans)


def f(x):
	return x[1]
n = int(input())
L = []
for i in range(n):
	order = [int(s) for s in input().split()]
	L.append(order)
L = sorted(L, key=f)
last = [L[0][1]]
item = 1
while item < n:
	while item < n - 1 and (L[item][1] <= last[-1] or L[item][0] <= last[-1]):
		item += 1
	if L[item][1] > last[-1] and L[item][0] > last[-1]:
		last.append(L[item][1])
	item += 1
print(len(last))


def __starting_point():
	n = int(input())
	orders = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		orders.append((b, a))
	sorders = sorted(orders)
	cnt = 0
	now = 1
	for i in range(0, len(sorders)):
		if sorders[i][1] > now or i == 0:
			cnt += 1
			now = sorders[i][0]
	print(cnt)
__starting_point()


n = int(input())
a = []
for _ in range(n):
	(x, y) = map(int, input().split())
	a.append((x, y))
a = sorted(a, key=lambda y: (y[0], y[1] - y[0]))
prev = (0, 0)
orders = 0
for order in a:
	(s, e) = order
	if s > prev[1]:
		prev = order
		orders += 1
	elif e < prev[1]:
		prev = order
print(orders)


n = int(input())
a = []
for i in range(0, n):
	x = list(map(int, input().split()))
	a.append(x)
a.sort(key=lambda x: x[1])
count = 1
r = a[0][1]
for i in range(1, n):
	if a[i][0] > r:
		r = a[i][1]
		count += 1
print(count)


n = int(input())
a = []
for i in range(n):
	temp = list(map(int, input().split()))
	temp.reverse()
	a.append(temp)
a.sort()
ans = 0
curr = 0
for i in range(len(a)):
	if a[i][1] > curr:
		ans += 1
		curr = a[i][0]
print(ans)


n = int(input())
job = []
cnt = 1
for i in range(n):
	(l, r) = map(int, input().split())
	job.append([l, r])
job.sort(key=lambda x: x[1])
prev = job[0][1]
for i in range(1, n):
	if job[i][0] > prev:
		cnt += 1
		prev = job[i][1]
print(cnt)


import os, sys
from collections import defaultdict, Counter, deque
from io import BytesIO, IOBase
from math import gcd, ceil

def lcm(a, b):
	return a * b // gcd(a, b)
MAXN = 100001
spf = [0 for i in range(MAXN)]

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def main():
	n = int(input())
	x = []
	z = defaultdict(list)
	m = 0
	for j in range(n):
		(a, b) = map(int, input().split())
		x.append([a, b])
	x.sort(key=lambda xx: xx[1])
	p = 0
	an = 0
	for i in range(n):
		if x[i][0] > p:
			an += 1
			p = x[i][1]
	print(an)
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()


n = int(input())
t = [list(map(int, input().split(' '))) for i in range(n)]
last = 0
count = 0
for i in sorted(t, key=lambda x: x[1]):
	if last < i[0]:
		last = i[1]
		count += 1
print(count)


n = int(input())
array = []
for k in range(n):
	a = list(map(int, input().split()))
	array.append((a[1], a[0]))
array.sort()
c = 1
end = array[0][0]
for k in range(1, n):
	if array[k][1] > end:
		c += 1
		end = array[k][0]
print(c)


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	tup = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda xx: xx[1])
	(ans, j) = ([0] * (n + 1), 0)
	for (ind, i) in enumerate(tup):
		while tup[j][1] < i[0]:
			ans[j + 1] = max(ans[j + 1], ans[j])
			j += 1
		ans[ind + 1] = ans[j] + 1
	print(max(ans))
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()


orders = []
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	orders.append([l, r])
orders.sort()
count = 0
while len(orders) > 1:
	if orders[-2][0] == orders[-1][0]:
		orders.pop(-2) if orders[-2][1] > orders[-1][1] else orders.pop(-1)
	elif orders[-2][1] >= orders[-1][0]:
		orders.pop(-2)
	else:
		orders.pop(-1)
		count += 1
if len(orders) == 1:
	count += 1
print(count)


n = int(input())
data = []
for num in range(n):
	t = input()
	(l, r) = t.split(' ')
	l = int(l)
	r = int(r)
	data.append((l, r))
data = sorted(data, key=lambda s: s[1])
num = 1
ci = data[0]
for item in data:
	(il, ir) = item
	(cl, cr) = ci
	if il > cr:
		ci = item
		num += 1
print(num)


n = int(input())
ls = []
for i in range(n):
	(l, r) = map(int, input().split())
	ls.append([r, l])
ls.sort()
ans = 1
end = ls[0][0]
for i in range(1, n):
	if ls[i][1] > end:
		ans += 1
		end = ls[i][0]
print(ans)


n = int(input())
L = []
r = []
m = []
for i in range(n):
	ch = input()
	L = [int(i) for i in ch.split()]
	l = L[0]
	r = L[1]
	m.append((r, l))
m.sort()
x = m[0][0]
nb = 1
for i in range(1, n):
	if m[i][1] > x:
		x = m[i][0]
		nb += 1
print(nb)


def key_tri(argument):
	return argument[1]
n = int(input())
L = [list(map(int, input().split())) for _ in range(n)]
L.sort(key=key_tri)
r = 1
t = L[0][1]
for k in range(1, n):
	if L[k][0] > t:
		r += 1
		t = L[k][1]
print(r)


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

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

def S():
	return str(input())

def L():
	return list(R())
from collections import Counter
import math
import sys
from itertools import permutations
n = I()
a = []
for _ in range(n):
	(b, c) = R()
	a.append([c, b])
a.sort()
(c, b) = a[0]
cnt = 1
for i in range(1, n):
	(x, y) = a[i]
	if y > c:
		(c, b) = (x, y)
		cnt += 1
print(cnt)


n = int(input())
a = []
for i in range(n):
	(l, r) = map(int, input().split())
	a.append([l, r])
a.sort(key=lambda x: x[1])
tmp = a[0][1]
tot = 1
for i in range(1, len(a)):
	if tmp < a[i][0]:
		tot += 1
		tmp = a[i][1]
print(tot)


def solve(tasks):
	if not tasks:
		return 0
	tasks.sort(key=lambda x: x[1])
	curr = tasks[0][1]
	count = 1
	for i in range(1, len(tasks)):
		if tasks[i][0] > curr:
			curr = tasks[i][1]
			count += 1
	return count
n = int(input())
tasks = []
for _ in range(n):
	task = list(map(int, input().split()))
	tasks.append(task)
print(solve(tasks))


import sys
n = int(sys.stdin.readline())
orders = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
orders.sort(key=lambda x: x[1])
prev_r = None
count = 0
for (l, r) in orders:
	if not prev_r or prev_r < l:
		count += 1
		prev_r = r
print(count)


n = int(input())
l = []
for i in range(n):
	s = input()
	temp = s.split()
	temp1 = [int(i) for i in temp]
	l.append(temp1)
l = sorted(l, key=lambda x: x[1])
cnt = 1
prev = l[0][1]
for i in range(1, len(l)):
	if l[i][0] > prev:
		cnt = cnt + 1
		prev = l[i][1]
print(cnt)


def second(x):
	return x[1]
n = int(input())
arr = []
for i in range(n):
	(a, b) = map(int, input().split())
	arr.append([a, b])
arr.sort(key=second)
ans = 1
till = arr[0][1]
for i in range(n):
	if arr[i][0] > till:
		ans += 1
		till = arr[i][1]
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
moves = []
for i in range(n):
	(a, b) = map(int, input().split())
	moves.append((b, a))
moves.sort()
user = 0
no = 0
for i in range(n):
	m = moves[i]
	if user < m[1]:
		user = m[0]
		no += 1
print(no)


times = []
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	times.append([a, b])
times.sort()
times = times[-1::-1]
(a, b) = (times[0][0], times[0][1])
cnt = 1
for i in range(1, len(times)):
	cur = times[i]
	(start, end) = (cur[0], cur[1])
	if start < a and end < a:
		cnt += 1
		a = start
		b = end
print(cnt)


n = int(input())
rg = []
for i in range(n):
	(a, b) = map(int, input().split())
	rg.append((a, b))
rg.sort()
last = rg[0][1]
ans = 1
for i in rg[1:]:
	if i[0] > last:
		last = i[1]
		ans += 1
	elif i[1] < last:
		last = i[1]
print(ans)