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