Hide

Problem F
Wi Know

You are the boss of Wi Know, an upstanding company in information theory, especially in message encryption.

The counter-counter-intelligence branch of your upstanding company managed to intercept a message sent by the counter-intelligence agency of the local Helsinkian government. This message is, of course, of utmost importance, and its content can probably be used for the “greater good” later. The message is a sequence S of N positive integers not greater than N, indexed from 1 to N. Let Si be the ith integer of S.

As the first step to mine useful information from this message, you first have to find patterns in it. At the moment, the pattern we’re interested in is whether there exists two different integers A and B such that the pattern A,B,A,B appears as a (not necessarily contiguous) subsequence of the original message. That is, whether there exists four indices 1c<d<e<fN such that Sc=Se, Sd=Sf, and ScSd.

Your task is to find such a pattern, if any, and print both A and B. If there are multiple such pairs (A,B), find the lexicographically smallest one. That is, if there are multiple such pairs (A,B), print the one whose A is minimized. If there are still multiple such patterns, print the one whose B is minimized.

Input

The first line contains a non-negative integer 4N400000, giving the number of integers in S. Thereafter follow N lines, the ith line contains a single integer 1SiN.

Output

If AB exists and the pattern A,B,A,B appears as a subsequence of S, you should print two integers A and B on a single line separated by a single space, denoting the lexicographically smallest pair of (A,B) as described in the problem statement. Otherwise, if there is no such pair, you should print a single integer 1.

Sample Input 1 Sample Output 1
8
1
3
2
4
1
5
2
4
1 2
Sample Input 2 Sample Output 2
8
1
2
3
4
5
6
7
1
-1

Sample Input 3 Sample Output 3
4
2
1
2
1
2 1
Hide

Please log in to submit a solution to this problem

Log in