Это сложная версия задачи. Разница между версиями заключается в ограничениях на элементы массива. Вы можете делать взломы, только если обе версии задачи сданы.
Вам дан массив $$$[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$$$ раза.
Название |
---|