Марсиане активно занимаются межпланетной торговлей. А город Олимп-Сити, известный своим космодромом, давно стал местом, куда поступают товары со всех уголков Галактики. Чтобы перевозить еще больше грузов с далеких планет, марсианам необходимы быстрые космические корабли.
Группа ученых как раз проводит эксперименты, чтобы построить быстрый двигатель для нового космического корабля. В текущем эксперименте участвует последовательность из \(n\) элементарных частиц, где \(i\)-я частица имеет тип \(a_i\).
Назовем подотрезком последовательности частиц (\(a_1, a_2, \dots, a_n\)) последовательность (\(a_l, a_{l+1}, \dots, a_r\)) для некоторой левой границы \(l\) и правой границы \(r\) (\(1 \le l \le r \le n\)). Например, у последовательности \((1\ 4\ 2\ 8\ 5\ 7)\) ее подотрезком при \(l=2\) и \(r=4\) является последовательность \((4\ 2\ 8)\). Также скажем, что два подотрезка являются различными, если хотя бы одна из границ этих подотрезков не совпадает.
Обратите внимание, что подотрезки могут быть одинаковыми как последовательности, но при этом считаться различными. Например, возьмем последовательность \((1\ 1\ 1\ 1\ 1)\) и два подотрезка: один с \(l=1\) и \(r=3\), другой — с \(l=2\) и \(r=4\). Оба подотрезка равны \((1\ 1\ 1)\), но при этом считаются различными, поскольку их левая и правая границы не совпадают.
Ученые хотят провести реакцию и получить два различных подотрезка одинаковой длины. Обозначим эту длину \(k\). При этом полученная пара подотрезков должна быть гармоничной, т. е. для некоторого \(i\) (\(1 \le i \le k\)) должно оказаться так, что типы частиц на \(i\)-й позиции совпадают. Например, пара подотрезков \((1\ 7\ 3)\) и \((4\ 7\ 8)\) гармонична, т. к. у обоих подотрезков на второй позиции стоит \(7\), а пара подотрезков \((1\ 2\ 3)\) и \((3\ 1\ 2)\) — нет.
Чем длиннее получатся гармоничные подотрезки, тем больше шансов, что ученые смогут сконструировать быстрый двигатель. Поэтому они попросили Вас помочь рассчитать максимальную возможную длину гармоничной пары из различных подотрезков.
Примечание
Первый пример изображен на рисунке ниже:
Как видно на рисунке, можно выбрать подотрезки \((2\ 1\ 3\ 4)\) и \((3\ 1\ 5\ 2)\), которые образуют гармоничную пару. Их длина равна \(4\), поэтому ответ равен \(4\).
Во втором примере можно взять два отрезка: первый — с \(l=1\) и \(r=5\), а второй — с \(l=2\) и \(r=6\). Как нетрудно видеть, эти отрезки образуют гармоничную пару и при этом считаются различными несмотря на то, что оба равны \((1\ 1\ 1\ 1\ 1)\).
В третьем примере можно заметить, что гармоничный отрезок построить нельзя, и ответ равен \(-1\).