Statement is not available in English language
3. Беспорядок в библиотеке
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В университетской библиотеке есть полка, на которой расположены $$$n$$$ книг. Каждая книга на этой полке — один из трех томов легендарной серии «Искусство программирования». Однако книги на полке никак не упорядочены, что усложняет процесс их выдачи читателям. Для решения этой проблемы руководство библиотеки приобрело робота, который может выполнять примитивные операции, описанные далее.

Для удобства пронумеруем все книги на полке слева направо числами от $$$1$$$ до $$$n$$$. За одну операцию робот может проехать вдоль полки слева направо и забрать с полки $$$1$$$-й, $$$2$$$-й и $$$3$$$-й тома в таком порядке. Иными словами, робот выберет некоторые книги с номерами $$$i$$$, $$$j$$$ и $$$k$$$ ($$$1 \le i \lt j \lt k \le n$$$), такие что $$$i$$$-я книга является $$$1$$$-м томом, $$$j$$$-я книга является $$$2$$$-м томом, а $$$k$$$-я книга является $$$3$$$-м томом.

К сожалению, в какой-то момент стало понятно, что в некоторых ситуациях у робота нет возможности забрать три тома с полки. Например, тома могут находиться в неправильном порядке, либо какой-то из томов может отсутствовать.

Ваша задача — найти максимальное количество томов, которые сможет забрать робот, выполнив некоторое количество описанных операций.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество книг на полке.

Вторая строка состоит из $$$n$$$ символов «1», «2» и «3», где $$$i$$$-й символ обозначает номер $$$i$$$-го тома.

Выходные данные

Выведите одно целое число — максимальное количество томов, которые сможет забрать робот, выполнив некоторое количество описанных операций.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Тесты из условияполная
15$$$n \le 3$$$первая ошибка
210 Гарантируется, что ответ не превосходит $$$3$$$ 1первая ошибка
310 Гарантируется, что ответ равен $$$0$$$ или $$$n$$$ 1первая ошибка
45 Гарантируется, что исходный порядок книг на полке выглядит как $$$11 \ldots 122 \ldots 2 33 \ldots 3$$$ (некоторые тома могут отсутствовать) первая ошибка
510$$$n \le 15$$$1первая ошибка
625$$$n \le 1\,000$$$1, 5первая ошибка
735нет1 – 6первая ошибка
Примеры
Входные данные
8
12123132
Выходные данные
6
Входные данные
3
123
Выходные данные
3
Входные данные
4
1311
Выходные данные
0
Входные данные
3
132
Выходные данные
0
Примечание

Рассмотрим первый пример. Сначала робот может забрать книги с номерами $$$1$$$, $$$2$$$ и $$$7$$$. После этого книжная полка будет выглядеть так: __1231_2 (здесь символом «_» обозначено пустое место). Затем робот может забрать книги с номерами $$$3$$$, $$$4$$$ и $$$5$$$. После этого книжная полка будет выглядеть так: _____1_2.

Во втором примере робот за одну операцию заберет все книги.

В третьем примере робот не сможет выполнить ни одну операцию, так как на полке нет $$$2$$$-го тома.

В четвертом примере робот не сможет выполнить ни одну операцию, так как книги на полке находятся в таком порядке, что робот не сможет забрать сначала $$$1$$$-й, затем $$$2$$$-й, после чего $$$3$$$-й том.