Description
Problem A - Homework
Roy Feng (馮謙) is a freshman at the Department of Computer Science, NTHU. This semester he takes the course "introduction to Programming." The professor (naughty HT) may give multiple assignments after a class, and each assignment may have a different deadline.
To become a top-level programmer, every day Roy completes at most one assignment as follows. Let S be the set of all unfinished assignments whose deadline has not yet passed. If S is empty, Roy will go out to find his “missing” girlfriend. Otherwise, his will arbitrarily pick an assignment A among S and complete it. With such a strategy, Roy might not be able to complete all assignments.
Given the schedule of assignments, your task is to compute the minimum and the maximum numbers of assignments Roy will be able to complete.
Input
The input consists of a single test case in the following format.
n
s1 t1
s2 t2
...
...
sn tn
The first line contains an integer n satisfying 1 ≤ n ≤ 100. n denotes the total number of assignments of the course. The next n lines show the schedule of assignments. The i-th line of them contains two integers si and ti satisfying 1 ≤ si ≤ ti ≤ 100, which mean that the i-th assignment is given on the si -th day of the semester, and its deadline is the end of the ti -th day.
Output
Print the minimum number and the maximum number of assignments Roy will be able to complete.