Cutting the curve

Given a simple orthogonal polygon with edges crossing the x axis, count peaks minimal under containment and peaks maximal under containment.

Medium7StackGeometrySortingImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

A computer graphics canvas is the rectangular area of a computer screen where you can draw. The canvas gives the position of every point by coordinates, like a two dimensional coordinate plane. The exact center of the canvas is the origin (0,0)(0, 0), the xx coordinate grows toward the right, and the yy coordinate grows toward the top.

Changsu drew one curve on the canvas with the mouse. The start point and the end point of the curve touch each other, and apart from that the curve never crosses or touches itself in between. After the curve is finished, erasing the area below the xx axis leaves a pattern of peaks whose boundaries never meet, as in the picture below. A peak is the area enclosed by the xx axis and a part of the curve whose start point and end point both lie on the xx axis. The example below has 5 peaks.

The computer stores a curve drawn with the mouse as a path built from vertical segments and horizontal segments. The curve Changsu drew is therefore stored as an orthogonal polygon whose boundary alternates once between a horizontal segment and a vertical segment. All vertices of this polygon are distinct, and no two edges meet unless they are consecutive. The picture below shows the same curve after the conversion.

Changsu wants to write a program that reads this orthogonal polygon and counts, among the peaks above the xx axis, how many peaks are contained in no other peak and how many peaks contain no other peak. In the picture above the first count is 3 and the second count is 4.

Input

The first line has the number of vertices NN (4N1064 \le N \le 10^6) of the orthogonal polygon that represents the curve.

Each of the next NN lines has the xx coordinate and the yy coordinate of one vertex, separated by a space, in the order the vertices are met while walking along the boundary of the polygon. The walking direction is the one that goes from bottom to top along the leftmost vertical segment. Every coordinate is an integer between 109-10^9 and 10910^9. No vertex has yy coordinate 00, and at least one edge meets the xx axis.

Output

On the first line print the number of peaks that are contained in no other peak and the number of peaks that contain no other peak, separated by a space, for the peak pattern made by the given orthogonal polygon.

Hint

The picture below draws the orthogonal polygon of the first example input.