Поликарп купил новую дорогую картину и решил показать своим \(n\) друзьям. Он повесил её у себя в комнате. Туда поочерёдно зашли и вышли \(n\) его друзей. В один момент в комнате было не больше одного человека. Иными словами, сначала зашёл и вышел первый друг, затем второй и так далее.
Известно, что в начале (до посещения друзей) в комнате висела картина. В конце (после \(n\)-го друга) оказалось, что она исчезла. В какой именно момент она пропала — информации нет.
Поликарп поочерёдно опросил друзей. У каждого он спросил: была ли картина, когда тот вошёл в комнату. Каждый друг ответил одно из трёх:
- нет (ответ кодируется символом 0);
- да (ответ кодируется символом 1);
- не помню (ответ кодируется символом ?).
Все, кроме вора, либо не помнят, либо сказали правду. Вор может сказать что угодно (любой из трёх вариантов).
Поликарп не может понять, кто вор. Он просит вас узнать количество тех, кого можно считать вором в соответствии показаниями.
Выходные данные
Вывести одно положительное (строго большее нуля) число – количество друзей, которые могли украсть картину на основании данных показаний.
Примечание
В первом случае ответ равен \(1\), так как у нас был ровно \(1\) друг.
Во втором случае аналогично.
В третьем случае подозреваемыми являются третий и четвёртый друг (считаем с единицы). Можно показать, что никто другой не мог быть вором.
В четвёртом случае нам абсолютно ничего не известно, поэтому подозреваем всех.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
0
1
1110000
?????
1?1??0?0
0?0???
??11
??0??
|
1
1
2
5
4
1
1
3
|