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

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

4 секунди
512 мегабайтів
Складна

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

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

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

Тобто, Шрек повинен визначити довжину найдовшої підпослідовності (не обов’язково з підрядкових позицій) x_1 x_2 \dots x_k of таку що для всіх 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] оскільки перший звук не має однакових сусідніх звуків.

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

Вхідні дані

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

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

1 \leq n \leq 10^6,

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

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

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