Graphics Quiz

In a long classroom, N desks are lined up in a row, and two students sit at each desk. Just by looking at a student's face, the professor can tell exactly what grade that student deserves, and each grade is shown in a different color (for example, if grade A is colored red, then B, C, and D are not colored red).

The quiz works as follows: the professor picks two desks, and from those two desks and every desk between them (that is, a contiguous range) points at exactly one student each. Today the professor brought only one colored pencil, so all pointed students must be given the same grade. A student can only be scored with the grade they truly deserve, so at every desk in the range there must be a student who deserves that grade for the professor to point at.

Find the maximum number of students the professor can score using a single grade, and which grade that is.

The first line contains the integer N (1 ≤ N ≤ 100,000).

Each of the next N lines contains the grades Ai and Bi that the two students at desk i deserve, separated by a space (1 ≤ Ai, Bi ≤ 5).

Print the maximum number of students that can be scored using a single grade, and that grade, separated by a space. If there are several answers, print the smallest grade.