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 it's 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
Pulkit Singhal:
20160426 09:06:01
Amazing Problem :) 

Kshitij Jain:
20150419 09:45:51
Why can't I submit solution for this problem ? 

Pushkar Mishra:
20141011 19:59:26
@chandravadan:


Chandravadan S:
20141011 19:59:26
Got WA at testcase#14.. Any tricky test cases? 

:D:
20141011 19:59:26
Very good problem. Really enjoyed analysis here.


Pushkar Mishra:
20141011 19:59:26
@Mitch Schwartz:


Mitch Schwartz:
20141011 19:59:26
An algorithm that is bestcase O(N) and worstcase O(N^2) should TLE, right?


Pushkar Mishra:
20141011 19:59:26
@Pankaj Saini:


PANKAJ SAINI:
20141011 19:59:26
I don't know what's going on....

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