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