Problem Description
Over the course of the year, as Mr Panda takes part in many activities such as projects and CCAs, his schedule is getting very packed. As the A-levels are coming near, he also needs to factor in a lot of homework and revision time into his schedule. Due to Mr Panda's lack of time management and addiction to the Binding of Isaac, he has been sleeping very late into the night and his panda eyes are getting from bad to worse! D:
His current schedule of N activities causes him to sleep very late and he needs to you to help him work out his daily schedule. Each activity i takes up a specific time period [Si,Ei] and once started must be carried out to completion. Given that Mr Panda can only carry out one activity at a time (he's a VERY BAD multitasker :P), help him find out what is the maximum the number of acitivites he can carry out in a single time period.
Input
The first line contains a single integer N.
The next N lines contain two integers each separated by a space. The two integers on the (i+1)th line represents Si and Ei
Output
The output should contain exactly one integer, the maximum number of activities that can be done in one time period.
Limits
Subtask 1(7%): 0 < N ≤ 20, 0 ≤ Si ≤ Ei ≤ 106
Subtask 2(17%): 0 < N ≤ 1000, 0 ≤ Si ≤ Ei ≤ 106
Subtask 3(27%): 0 < N ≤ 100000, 0 ≤ Si ≤ Ei ≤ 106
Subtask 4(49%): 0 < N ≤ 100000, 0 ≤ Si ≤ Ei ≤ 109
Subtask 5(0%): Sample
Sample Input
5
5 7
1 4
6 8
2 6
7 9
Sample Output
3
Explanation: Pick activities 1,2,5