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.