Кевин только что получил свои неутешительные результаты по Олимпиаде по Идентификации Коров в США (USAICO) в виде бинарной строки длины n. Каждый символ строки Кевина представляет собой результат Кевина на одном из n вопросов олимпиады — '1' если корова была определена правильно и '0' в противном случае.

Тем не менее не всё потеряно. Кевин — большой любитель нестандартного мышления, и он считает, что его результат должен быть не суммой его очков, а максимальной длиной чередующейся подпоследовательности его строки. Здесь мы определяем чередующуюся подпоследовательность строки как подпоследовательность (необязательно из соседних элементов), в которой никакие два последовательных элемента не равны. Например, {0, 1, 0, 1}, {1, 0, 1}, и {1, 0, 1, 0} — чередующиеся подпоследовательности, в то время как {1, 0, 0} и {0, 1, 0, 1, 1} таковыми не являются.

Кевин, будучи ещё тем хитрецом, готов взломать базу данных USAICO, чтобы улучшить свой результат. Для того чтобы провернуть дело незаметно, он решил, что инвертирует ровно одну подстроку, то есть возьмёт несколько последовательных элементов строки своего результата и изменит все '0' в этой подстроке на '1' и наоборот. Кевин хочет знать максимально возможную длину самой длинной чередующейся подпоследовательности, которую может иметь строка с его результатами после одной операции инвертирования.