<PREV Problem:
NEXT>
Solved by 48 users: Evgeny, Pupyrev, marian, NSI, Shurik, naum, LPN_3, programer, Jarovit, yangzhe1990, Elwin, wojtekt, tomek, szywrz, venkatkenshi, zmy, relja, Cheryl, RAVEman, rvashegin, WsemirZ, obtuseSword, littleboy, pmnox, defrager, UdH-WiNGeR, regal, Al.Cash, vitar, Quazar, vi002, tourist, mathematic, JohnJones_001, Kuznetsov_S, LiuChenheng, Dest, Jacob, opsupwow, NIGHTFIT, Azizkhan, Robert_Gerbicz, regmar, murphy, Ramazan_S, adamant, Chmeli_BSU, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Intervals

Time limit = 5 second(s)

Memory limit = 64 Mb

There are N intervals (a_i, b_i). a_i and b_i are integers not exceeding 2'000'000'000 by their absolute value.

Your task is to find the number of ways we could choose a maximum subset of disjoint intervals.

Input First line contains N (1 ≤ N ≤ 100000) In the next N lines coordinates of the ends of intervals are given. Each line contains two numbers a_i, b_i serarated with a space.

Output The only number — unknown number of ways. It's known it doesn't exceed 10^18.

Input#1
4
1 2
1 4
3 5
4 5
Output#1
3

Input#2
4
1 2
1 2
2 3
2 3
Output#2
4

Author:
Zhuk Sergey, IV MIPT Contest
11 April 2004

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.80.60.91