HSEQ - Heavy Sequences

no tags 

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 <= 105 ).
The second line of input contains a sequence S of N integers, ( 0 <= Si <= 109 ).

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

hide comments
linkret: 2020-08-12 16:57:53

The official solution (and the test cases) are faulty. For example, for the example
6
1 4 4 4 1 4

The official solution prints "4" instead of "1 4". They both have weights 1*4=2*2=4, but "1 4" is lexicographically lesser. The problem is, the official solution computes that the "maximal weight" of the "4 4 4 4" is 3, and "1 4 1 4" is 2. So you need to make your solution wrong like that in order to get accepted. (just reduce the number of occurances by 1)

Ahmed Kamel [ahm.kam_92]: 2011-08-22 15:26:49

Can the occurrences of any continuous subsequence over lap ?

Ex: "1111"
the number of occurrences of "11" is 2 or 3 ?

----------------
answer: 3, the continuous subsequences may overlap

Last edit: 2009-12-23 16:13:57

Added by:gustav
Date:2009-12-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 PERL6
Resource:co-author: Stjepan Glavina