SBO - MAXIMUM RARITY


Given a sequence of numbers, each number between 1 and 100000 (inclusive), find the contiguous subsequence with maximum rarity.

The rarity of a sequence is defined as the count of numbers which appear only once in that sequence. For example, let's consider the following sequence:

1 1 2 5 1 16 5

The rarity of the subsequence 1 1 2 5 is 2. This is because 2 and 5 are the only numbers which appear just once. 1 appears twice in the sequence, hence doesn't contribute to its rarity. The rarity of subsequence 1 16 5 is 3 as each of the numbers appears only once. The maximum rarity achieved by any contiguous subsequence in the sequence 1 1 2 5 1 16 5 is 4. This is the rarity of 2 5 1 16.

Your task is to find the contiguous subsequence with maximum rarity and output that rarity value. You don't have to output the subsequence itself.

Input

The first line of input will contain an integer N. N is the count of numbers in the input sequence.

1 <= N <= 500000.

The next line will contain the sequence of numbers. Each number in the sequence is an integer between 1 and 100000.

Output

The maximum rarity that any contiguous subsequence possesses.

Example

Input 1:
7
1 1 2 5 1 16 5

Output 1:
4
Input 2:
3
1 2 3

Output 2:
3
Input 3:
10
2 1 4 1 5 6 7 1 8 2

Output 3:
6
Input 4:
20
3 4 14 14 9 7 11 7 15 13 9 9 14 9 13 10 13 9 5 4

Output 4:
7

Explanation

Input 2: The maximum rarity is achieved by the sequence itself.

Input 3: The maximum rarity is achieved by the subsequences 1 4 1 5 6 7 1 8 2, 4 1 5 6 7 1 8 2 and 5 6 7 1 8 2. All the three contiguous subsequences have rarity 6.

Input 4: The maximum rarity is achieved by the subsequence 11 7 15 13 9 9 14 9 13 10 13 9 5 4. This sequence has 7 numbers which appear only once in it, i.e., 11, 7, 15, 14, 10, 5, 4.


hide comments
Pushkar Mishra: 2014-10-11 19:59:26

@Pankaj Saini:
Even though your algorithm is correct, it isn't efficient. If you look at the constraints, the complexity has to be less than O(N^2) to get accepted. Your DP is definitely (N^2) and hence inefficient.

PANKAJ SAINI: 2014-10-11 19:59:26

I don't know what's going on....

solved it in many ways still TLE.. even in DP
:P

any hint??

Pushkar Mishra: 2014-10-11 19:59:26

Sample test case 4 has been added.


Added by:Pushkar Mishra
Date:2013-06-10
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own