Шрекова пісня болота

Обмеження: 4 сек., 512 МіБ

У далекому королівстві Дюлок, Шрек виявив чарівну мелодію, сховану серед стародавніх Болотяних Пісень. Однак ця мелодія записана як послідовність чисел, що представляють кумедні квакання жаб і шелест листя. Щоб розкрити її таємниці, Шреку потрібно розшифрувати найдовший повторюваний шаблон у цій містичній послідовності, дотримуючись певних правил.

Шрекова послідовність мелодії \(s\), складається з різних звуків, кожен із яких представлений цілим числом. Пісня містить \(n\) звуків у цілому.

Шрек повинен знайти найдовшу можливу підпослідовність, яка дотримується суворої Дюлокської гармонії. Щоб створити Дюлокську гармонію, повинна виконуватись така умова: кожен звук повинен мати сусіда в обраній підпослідовності, однакового до нього ж.

Тобто, Шрек повинен визначити довжину найдовшої підпослідовності (не обов’язково з підрядкових позицій) \(x_1 x_2 \dots x_k\) of \(s\) таку що для всіх \(1 \le i \le k\) виконується \(x_i=x_{i-1}\) або \(x_i=x_{i+1}\).

Наприклад, Шрек може вибрати підпослідовності \([1, 1, 1, 2, 2]\), \([4, 4, 4, 4, 4]\), але не може \([1, 2, 2, 1, 1]\) оскільки перший звук не має однакових сусідніх звуків.

Допоможіть Шреку розкрити цю зачаровану мелодію!

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість звуків у пісні Шрека.

У другому рядку задано \(n\) цілих чисел \(s_1, s_2, \dots, s_n\), що описують пісню Шрека.

Вихідні дані

У першому рядку виведіть єдине число — довжину найдовшої підпослідовності \(s\), яка є Дюлокською гармонією. Якщо такої підпослідовності не існує — виведіть 0.

Обмеження

\(1 \leq n \leq 10^6\),

\(-10^{9} \leq s_i \leq 10^{9}\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
9 1 2 3 1 3 1 2 3 2	5

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 3 4 10 1 -3 5	0

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 1 1	3

Примітки

У першому прикладі, найдовша підпослідовність, що є Дюлокською гармонією це: \(s_1 s_4 s_6 s_7 s_9\) = [1, 1, 1, 2, 2].

У другому прикладі, такої підпослідовності не існує.