Найдовша альтернативна послідовність з одним переворотом#9556
У Мурада є колекція монет, розміщених у ряд на столі. Кожна монета показує або герб (), або решку (). Мурад хоче отримати найбільшу можливу підрядну альтернативну послідовність монет (наприклад, або ), тобто таку, що сусідні монети відрізняються.
Для цього він може вибрати не більше одного підмасиву монет і перевернути всі його монети (змінити герб на решку і навпаки). Допоможіть Мураду визначити максимальну довжину підрядної альтернативної послідовності монет, яку можна отримати, виконавши не більше одного такого перевороту (або зовсім без перевороту).
Перший рядок містить ціле число (1 \leq N \leq 10^5) — кількість монет.
У наступному рядку міститься чисел, кожне з яких або .
Виведіть максимальну довжину підрядної альтернативної послідовності, яку можна отримати, перевернувши не більше одного підмасиву.
Приклад 1
Приклад 2
Перший тестовий випадок:
Якщо перевернути монети з індексів по , масив стане: 1\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 1\ 0. Виділена частина є альтернативною та має довжину .
Другий тестовий випадок:
Треба змінити лише елемент з індексом : 1\ 0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1.