Given a sequence S of N integers, indexed from 0 to N-1, we define the weight of its continuous subsequence as the product of its length and its number of occurrences in the main sequence, and in case of uniqueness, we say its weight is 0.

Let's see an example:

   N = 5
   S = { 1, 7, 3, 1, 7 }

The continuous subsequence S[ 0, 1 ], which is equal to { 1, 7 }, has a weight of 4, by definition. The continuous subsequence S[ 2, 2 ] thus has a weight of 0.

Your task is to find the continuous subsequence of maximum weight. To break ties, choose the lexicographically smallest of the candidates ( a sequence A is lexicographically smaller than another sequence B if the first element at which they differ is smaller in A, or if A is a prefix of B ).

If the maximum weight of all the continuous subsequences is 0, we say the sequence is invalid.

Input

The first line of input contains a single integer, N ( 1 <= N <= 10⁵ ).
The second line of input contains a sequence S of N integers, ( 0 <= S_i <= 10⁹ ).

Output

In case of an invalid subsequence, output -1.
A continuous subsequence of the input sequence with the property defined above.

Example

Input:
5
1 7 3 1 7
 
Output:
1 7