$$$n$$$ игроков собираются провести турнир по игре «камень-ножницы-бумага». Как вы наверное знаете, при игре один на один в камень-ножницы-бумагу каждый из игроков выбирает себе предмет независимо друг от друга. Затем результат определяется в зависимости от выбранных предметов: "бумага" побеждает "камень", "камень" побеждает "ножницы", "ножницы" побеждают "бумагу", и два одинаковых предмета приводят к ничьей.

В начале турнира все игроки будут стоять в ряд. Они пронумерованы по возрастанию от $$$1$$$ до $$$n$$$ от самого левого игрока к самому правому. Каждый игрок имеет заранее выбранный предмет, который он будет использовать в каждой игре на протяжении всего турнира. Вот как будет проводиться турнир:

• Если остался только один игрок, он объявляется победителем.
• Иначе, в ряду выбираются произвольно два соседних игрока. Они играют следующий матч. Проигравший игрок выбывает из турнира и покидает свое место в ряду (его бывшие соседи становятся соседями). Если игра завершилась ничьей, проигравший игрок определяется подбрасыванием монеты.

Организаторы знают о предпочтительных предметов всех игроков. Они хотят узнать общее количество игроков, у которых есть шанс стать победителем турнира (это значит, что есть подходящий способ выбрать порядок игр и манипулировать бросками монет). Тем не менее, некоторые игроки все еще оптимизируют свою стратегию и могут сообщить организаторам о своих новых предпочтительных предметах. Можете ли вы найти количество возможных победителей после каждого такого запроса?