AKVISM03 - Kyle Makes a List

Kyle got "N" pairs (Ai, Bi) such that 0 <= i < N and Ai < Bi. He wants to make a list out of these "N" pairs. But there is a limitation on it, If (x, y) comes after (a, b) in the list, then x must be greater than b.

For example:

  • (1, 3), (5, 8), (13, 15) is a valid list.
  • (1, 3), (2, 4), (5, 8) is not a valid list.

Your task is to form the longest list that is possible using the "N" pairs.

Input

First line will contain "N", the number of pairs Kyle has. Each of the next "N" lines will contain two integers Ai and Bi.

Output

Output a single integer, length of the longest list it is possible to make using these pairs.

Constraints

1 <= N <= 1000

0 <= Ai < Bi <= 109

Example

Input:
5
4 8
1 2
2 8
13 20
7 14

Output:
3

Explanation

Longest possible list is (1, 2), (4, 8) and (13, 20).


Added by:Ankit Kumar Vats
Date:2013-07-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.