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: 2016-04-26 09:06:01

Amazing Problem :)

Kshitij Jain: 2015-04-19 09:45:51

Why can't I submit solution for this problem ?

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

@chandravadan:
your program only produced the correct answer for one of the many test cases.

Last edit: 2013-07-08 15:52:48
Chandravadan S: 2014-10-11 19:59:26

Got WA at testcase#14.. Any tricky test cases?

:D: 2014-10-11 19:59:26

Very good problem. Really enjoyed analysis here.

I took the liberty to edit the description implementing Mitch's remarks (comment now hidden).

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

@Mitch Schwartz:
Yes. An algorithm with worst case complexity of O(n^2) won't pass.

Mitch Schwartz: 2014-10-11 19:59:26

An algorithm that is best-case O(N) and worst-case O(N^2) should TLE, right?

Edit: Thanks for the reply.

Last edit: 2013-06-23 00:16:57
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??


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