408931: GYM103383 4 Любовь и двери
Description
Коварный Джафар разделил Аладдина и Жасмин, заманив их в разные концы длинного коридора и заперев между ними $$$n$$$ дверей. Теперь, чтобы вновь увидеться, влюблённым необходимо открыть все эти двери по очереди.
Каждая из дверей является золотой или серебряной и открывается одним из двух ключей из соответствующего материала, причём может быть открыта этим ключом с любой стороны. Используя магию джинна, Аладдин может сделать так, чтобы у него и Жасмин появилось по одному ключу разного типа. Это значит, что если у Аладдина появится золотой ключ, то у Жасмин — серебряный, а если у Аладдина будет серебряный ключ, то у Жасмин — золотой.
Помимо этого, Аладдин может попросить джинна изменить материал любой из дверей (с золотого на серебряный или наоборот). Но каждую такую операцию джинн будет выполнять ровно одну минуту.
После того, как джинн закончит изменять двери, Аладдин и Жасмин начнут открывать их, двигаясь навстречу друг другу. Будем считать, что открытие дверей и перемещение между ними происходит мгновенно. Через какое наименьшее время они смогут наконец встретиться?
Входные данныеПервая строка входных данных содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — количество дверей. Следующие $$$n$$$ строк содержат по одной цифре $$$1$$$ или $$$2$$$. Эти цифры определяют порядок следования дверей в коридоре. Единица значит, что соответствующая дверь золотая, а двойка — что серебряная.
Выходные данныеВыведите одно число — наименьшее количество минут, через которое будут открыты все двери.
Система оценкиРешения, правильно работающие для случаев, в которых количество золотых дверей не превосходит трёх, а количество дверей не больше 10, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых общее количество дверей не превосходит 100, получат не менее 32 баллов.
Решения, правильно работающие для случаев, в которых общее количество дверей не превосходит 1000, получат не менее 56 баллов.
ПримерыВходные данные8 1 2 2 1 2 1 1 1Выходные данные
2Входные данные
4 2 1 1 1Выходные данные
0Входные данные
9 1 1 1 1 2 1 1 1 1Выходные данные
1Примечание
В первом примере нужно выдать тому, кто находится у первой двери серебряный ключ, а тому, кто у последней — золотой. Далее нужно изменить тип первой и пятой двери, тогда последовательность дверей станет такой: 2, 2, 2, 1, 1, 1, 1, 1.. После этого ключами можно будет открыть все двери. Можно показать, что быстрее, чем за две операции, справится не выйдет.