#P1446D2. Frequency Problem (Hard Version)

    ID: 1149 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>data structuresgreedytwo pointers*3000

Frequency Problem (Hard Version)

Description

This is the hard version of the problem. The difference between the versions is in the constraints on the array elements. You can make hacks only if all versions of the problem are solved.

You are given an array [a1,a2,,an][a_1, a_2, \dots, a_n].

Your goal is to find the length of the longest subarray of this array such that the most frequent value in it is not unique. In other words, you are looking for a subarray such that if the most frequent value occurs ff times in this subarray, then at least 22 different values should occur exactly ff times.

An array cc is a subarray of an array dd if cc can be obtained from dd by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

The first line contains a single integer nn (1n2000001 \le n \le 200\,000) — the length of the array.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ain1 \le a_i \le n) — elements of the array.

You should output exactly one integer  — the length of the longest subarray of the array whose most frequent value is not unique. If there is no such subarray, output 00.

Input

The first line contains a single integer nn (1n2000001 \le n \le 200\,000) — the length of the array.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ain1 \le a_i \le n) — elements of the array.

Output

You should output exactly one integer  — the length of the longest subarray of the array whose most frequent value is not unique. If there is no such subarray, output 00.

Samples

样例输入 1

7
1 1 2 2 3 3 3

样例输出 1

6

样例输入 2

10
1 1 1 5 4 1 3 1 2 2

样例输出 2

7

样例输入 3

1
1

样例输出 3

0

Note

In the first sample, the subarray [1,1,2,2,3,3][1, 1, 2, 2, 3, 3] is good, but [1,1,2,2,3,3,3][1, 1, 2, 2, 3, 3, 3] isn't: in the latter there are 33 occurrences of number 33, and no other element appears 33 times.