HSEQ - Heavy Sequences
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
|
|
Ahmed Kamel [ahm.kam_92]:
2011-08-22 15:26:49
Can the occurrences of any continuous subsequence over lap ?
|
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 |