У далекому королівстві Дюлок, Шрек виявив чарівну мелодію, сховану серед стародавніх Болотяних Пісень. Однак ця мелодія записана як послідовність чисел, що представляють кумедні квакання жаб і шелест листя. Щоб розкрити її таємниці, Шреку потрібно розшифрувати найдовший повторюваний шаблон у цій містичній послідовності, дотримуючись певних правил.
Шрекова послідовність мелодії , складається з різних звуків, кожен із яких представлений цілим числом. Пісня містить звуків у цілому.
Шрек повинен знайти найдовшу можливу підпослідовність, яка дотримується суворої Дюлокської гармонії. Щоб створити Дюлокську гармонію, повинна виконуватись така умова: кожен звук повинен мати сусіда в обраній підпослідовності, однакового до нього ж.
Тобто, Шрек повинен визначити довжину найдовшої підпослідовності (не обов’язково з підрядкових позицій) 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.
Приклад
Приклад 1
Приклад 2
У першому прикладі, найдовша підпослідовність, що є Дюлокською гармонією це: s_1 s_4 s_6 s_7 s_9 = [1, 1, 1, 2, 2].
У другому прикладі, такої підпослідовності не існує.