Function Loop Detection

Interview

Time limit1sMemory limit1024 MB

Summary

Find the segment of distinct function names that repeats consecutively the most times in a call list, then print its length, repeat count, and contents.

Level: Medium6 of 10
Topics: Array, Hash map, Sliding window
Solved: No attempts yet

Problem

Ikjun has a function call list that records the names of the functions called during a program run. He wants to find the segment of consecutive calls that repeats the most times in a row, where every element in the segment is distinct.

For example, $[A, B, C, A, B, C]$ contains the segment $[A, B, C]$ twice.

In $[A, B, C, B, A, B, C, B]$ , the segment $[A, B, C, B]$ repeats consecutively, but the name $B$ appears twice in it, so it does not satisfy the condition.

Input

The first line contains an integer $N$ . ( $1 \leq N \leq 100\,000$ )

The second line contains $N$ strings $S_i$ separated by spaces. Each string consists of uppercase English letters only. ( $1 \leq |S_i| \leq 10$ )

Output

The first line prints the length and the number of repetitions of the segment that appears first among the segments repeated the most times.

The second line prints that function call segment, with its elements separated by spaces.

If no segment repeats more than once, print only -1.

Hint

$|S|$ is the length of the string $S$ .

Examples4

Example 1
Input
```
6
O IK O IK JUN JUN
```
Expected output
```
2 2
O IK
```

Example 2

Input

15
A B C B C A B C B C A B C B C

Expected output

2 2
B C

Example 3
Input
```
5
A A A A A
```
Expected output
```
1 5
A
```
Example 4
Input
```
8
A B C B A B C B
```
Expected output
```
-1
```