Starting a Scenic Railroad Service

Jim works for a railroad company and is planning a new tourist train service. He is sure that a route along a scenic valley will draw a big crowd, but he does not know how big.

A market survey came back with an estimated list of the travel sections the passengers will book. From that list Jim wants the smallest number of seats that meets the demand.

Preparing one seat for every passenger costs far too much. Two passengers whose travel sections do not overlap can share a single seat, and that cuts the cost a lot.

Two seat assignment policies are under consideration. The view from a train window depends on the seat position, so passengers are happier when they pick a seat themselves. Under policy 1 a passenger chooses an arbitrary seat among the seats that are still free at the moment of the reservation. The order of the reservations is unknown, so every possible order has to be counted.

Under policy 2 passengers do not choose their seats. The railroad operator decides every seat assignment after all reservations are complete. This policy reduces the number of required seats considerably.

Write a program that tells Jim how far apart the two policies are, by computing the number of seats required under each one.

Consider a case with four stations S1, S2, S3, S4 and four expected passengers p1, p2, p3, p4. Passenger p1 rides from S1 to S2, p2 rides from S2 to S3, p3 rides from S1 to S3, and p4 rides from S3 to S4.

The sections of p1 and p2 do not overlap, the section of p3 overlaps both of them, and the section of p4 overlaps nobody. A passenger who alights at a station and a passenger who boards at that same station share no part of the route, so one seat holds both.

Check whether two seats are enough under policy 1. If p1 books first, either of the two seats can be chosen. If p2 books second, the section does not overlap that of p1, so the same seat can be booked, but the other seat may look more attractive to p2. If p2 reserves a seat different from the seat of p1, no seat is left for p3 between S1 and S3 (Figure I.1).

Figure I.1. With two seats

With three seats, p3 finds a seat under any combination of reservations by p1 and p2. Passenger p4 also books a seat, because no other passenger travels between S3 and S4 (Figure I.2).

Figure I.2. With three seats

For this travel list three seats are enough under policy 1, over all possible reservation orders and seat preferences.

Deciding the seat assignments after all reservations are complete allows a tight assignment with only two seats under policy 2 (Figure I.3).

Figure I.3. Tight assignment to two seats

The input consists of a single test case in the following format.

n
a1 b1
.
.
.
an bn

The first line has an integer $n$, the number of passengers in the estimated list of travel sections ($1 \le n \le 200000$). Stations are numbered from 1 in their order along the route. Each of the following $n$ lines describes the travel of one passenger by two integers, the boarding station number $a_i$ and the alighting station number $b_i$ ($1 \le a_i < b_i \le 100000$). More than one passenger in the list may have the same boarding and alighting stations.

Print two integers $s_1$ and $s_2$ on one line in this order, separated by a space. $s_1$ is the number of seats required under policy 1 and $s_2$ is the number required under policy 2.