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
nikzad082_: 2020-09-27 16:57:21

Segment Tree & storing Prev
AC in first attempt :)

luka_dzimba911: 2018-07-22 15:48:37

Heads up do not put endl after printing answer it gives WA i got 6 WA's cuz of that a wasted 3hrs on that silly mistake

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

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