Graphics Quiz

Interview

Time limit1sMemory limit128 MB

Summary

For each of 5 grades, find the longest contiguous run of desks where at least one student has that grade, then output the best length and the smallest grade achieving it.

Level: Medium4 of 10
Topics: Array, Sliding window, Greedy
Solved: No attempts yet

Problem

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.

Input

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).

Output

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.

Examples3

Example 1
Input
```
1
1 5
```
Expected output
```
1 1
```
Example 2
Input
```
3
3 5
4 5
1 3
```
Expected output
```
2 5
```
Example 3
Input
```
4
2 1
3 2
5 3
2 5
```
Expected output
```
2 2
```