D2. Задача о частотах (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между версиями заключается в ограничениях на элементы массива. Вы можете делать взломы, только если обе версии задачи сданы.

Вам дан массив $$$[a_1, a_2, \dots, a_n]$$$.

Ваша цель — найти длину самого длинного подмассива этого массива такого, в котором наиболее часто встречающееся значение не единственно. Другими словами, вы ищете подмассив такой, что если в этом подмассиве наиболее часто встречающееся значение встречается $$$f$$$ раз, то как минимум $$$2$$$ разные значения должны встречаться в нем ровно $$$f$$$ раз.

Массив $$$c$$$ является подмассивом массива $$$d$$$, если $$$c$$$ может быть получен из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Входные данные

Первая строка содержит единственное целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

Выходные данные

Необходимо вывести ровно одно целое число — длину самого длинного подмассива массива, наиболее частое значение которого не является единственным. Если такого подмассива нет, выведите $$$0$$$.

Примеры
Входные данные
7
1 1 2 2 3 3 3
Выходные данные
6
Входные данные
10
1 1 1 5 4 1 3 1 2 2
Выходные данные
7
Входные данные
1
1
Выходные данные
0
Примечание

В первом примере подмассив $$$[1, 1, 2, 2, 3, 3]$$$ хороший, но $$$[1, 1, 2, 2, 3, 3, 3]$$$ нет: во втором число $$$3$$$ встречается $$$3$$$ раза, и ни один другой элемент не встречается $$$3$$$ раза.