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.
UserDateAttemptTimeCMSC
tomek`18 feb 2006`C++500.20218
Al.Cash`04 aug 2009`C++200.92277
mathematic`10 sep 2011`C++400.17311
adamant`19 feb 2015`C++700.87329
Quazar`29 jun 2011`C++1001.09334
Quazar`29 jun 2011`C++500.20338
Quazar`29 jun 2011`C++800.19340
marian`01 nov 2004`C++1?.??341
NIGHTFIT`27 mar 2012`C++800.27355
NIGHTFIT`27 mar 2012`C++700.27357
obtuseSword`05 may 2008`C++101.03359
JohnJones_001`10 sep 2011`C++400.23372
szywrz`18 feb 2006`C++100.21374
 C++ 35 Kylix 6 FPC 5 Java 3
` >  >  >  >  >  >  >  >  >  > `

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

 © acm.mipt DevGroupThe page was generated in 180ms