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

Difficulty: interview

Starter code:

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


r = lambda: list(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 = [tuple(map(int, input().split())) for _ in range(n)]
#print(a)
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)
    


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)




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)):
        #print(now)
        if sorders[i][1]>now or i==0:
            cnt += 1
            now = sorders[i][0]
    print(cnt)

__starting_point()

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)

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)


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)

"""
Codeforces Testing Round #12

Problem 597B. Restaurant

@author yamaton
@date 2015-11-11
"""

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(file=sys.stderr, *args, **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)


def __starting_point():
    main()

__starting_point()

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)

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)

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)

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



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)


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

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

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)

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

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

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