Название — это отсылка на самый первый Educational Round нашего авторского коллектива, Educational Round 18.
Есть мешок, в котором лежат разноцветные шары. Всего есть \(n\) различных цветов шаров, пронумерованные от \(1\) до \(n\). В мешке лежат \(\mathit{cnt}_i\) шаров цвета \(i\). Суммарное количество шаров в мешке нечетное (т. е. \(\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n\) нечетное).
За один ход можно выбрать два шара разных цветов и вынуть их из мешка.
В какой-то момент все оставшиеся в мешке шары станут одного цвета. Тогда вы больше не можете делать ходы.
Найдите любой возможный цвет оставшихся шаров.
Выходные данные
На каждый набор входных данных выведите одно целое число — любой возможный цвет оставшихся шаров после того как вы сделали какие-либо ходы и больше не можете делать ходы.
Примечание
В первом наборе входных данных ваш первый и единственный ход может быть одним из следующих:
- возьмем шары с цветами \(1\) и \(2\);
- возьмем шары с цветами \(1\) и \(3\);
- возьмем шары с цветами \(2\) и \(3\).
После хода останется ровно один шар. Его цвет может быть \(3, 2\) или \(1\) в зависимости от хода.
Во втором наборе не получится сделать ход вообще — есть всего один цвет шаров. Этот цвет \(1\).
В третьем примере можно удалять один шар цвета \(1\) и один шар цвета \(2\), пока не закончатся шары цвета \(1\). В конце останутся три шара цвета \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 1 1
1
9
2
4 7
|
3
1
2
|