Вам дан массив \(a_1, a_2, \ldots, a_n\).
За один ход можно выполнить любую из двух операций:
- Выбрать элемент из массива и удалить его из массива. В результате длина массива уменьшается на \(1\);
- Выбрать элемент из массива и увеличить его значение на \(1\).
Вы можете выполнять произвольное количество ходов. Если текущий массив оказался пустым, то больше ходов выполнять нельзя.
Ваша задача — найти минимальное количество ходов, которые необходимо выполнить, чтобы сумма элементов массива \(a\) стала делиться на \(3\). Возможно, вам понадобится \(0\) ходов.
Обратите внимание, что сумма элементов пустого массива (массива длины \(0\)) равна \(0\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество ходов.
Примечание
В первом наборе входных данных, изначально \(a = [2, 2, 5, 4]\). Один из оптимальных способов выполнения ходов:
- удалить \(4\)-й элемент и получить \(a = [2, 2, 5]\);
Таким образом сумма массива
\(a\) станет делиться на
\(3\) (действительно,
\(a_1 + a_2 + a_3 = 2 + 2 + 5 = 9\)).
Во втором наборе входных данных изначально сумма массива равна \(1+3+2 = 6\), что делится на \(3\). Таким образом, ходы не требуются. Следовательно, ответ равен \(0\).
В четвертом наборе входных данных изначально сумма массива равна \(1\), что не делится на \(3\). Удалением его единственного элемента вы получите пустой массив, поэтому его сумма равна \(0\). Следовательно, ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
4
2 2 5 4
3
1 3 2
4
3 7 6 8
1
1
4
2 2 4 2
2
5 5
7
2 4 8 1 9 3 4
2
4 10
|
1
0
0
1
1
2
1
1
|