A Sequence That Matches Front and Back

Time limit2sMemory limit128 MB

Summary

Choose how many elements to cut from the array's front so that, if the rest is a k-front-back sequence, k is as large as possible or no k exists. Return k and the cut count.

Level: Hard8 of 10
Topics: Array, String matching, Binary search
Solved: No attempts yet

Problem

A sequence $(a_1, a_2, \cdots, a_N)$ is called a k-front-back sequence if it satisfies the following property.

$(a_1, a_2, \cdots, a_k) = (a_{N-k+1}, a_{N-k+2}, \cdots, a_N), \quad 1 \le k < N$

When a sequence is a k-front-back sequence, the maximum value of k, denoted $k^*$ , is called the front-back coefficient of the sequence.

To make the front and back of a sequence match, we can cut off a contiguous prefix of the sequence.

For example, removing $(a_1, a_2)$ from $(a_1, a_2, \cdots, a_N)$ yields $(a_3, a_4, \cdots, a_N)$ .

How much of the prefix of the given sequence $(A_1, A_2, \cdots, A_N)$ should we cut off to maximize the front-back coefficient? There may be more than one way to do this. The cutting methods also include "cutting nothing."

Input

The first line contains $N$ . ( $2 \le N \le 1\,000\,000$ )

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces. ( $-2^{31} \le A_i \le 2^{31}-1$ )

Output

If cutting a prefix can produce a front-back sequence, output the maximum front-back coefficient after such a cut and the number of ways to make that cut, separated by a space. If no cut produces a front-back coefficient, output -1.

Examples3

Example 1
Input
```
12
1 4 8 4 7 3 4 7 4 8 4 7
```
Expected output
```
4 1
```
Example 2
Input
```
11
2 5 2 5 2 5 2 8 2 5 2
```
Expected output
```
3 3
```
Example 3
Input
```
10
0 1 2 3 4 5 6 7 8 9
```
Expected output
```
-1
```