Lordfantomchik

09.09.2021 02:38 •  Информатика

Шрифт PascalABS.NET B. Делимость

Ограничение времени 1 секунда

Ограничение памяти 256Mb

Ввод стандартный ввод или input.txt

Вывод стандартный вывод или output.txt

Вам дано число, состоящее из m цифр, без лидирующих нулей. За один ход вы можете поменять местами две соседние цифры этого числа, но после хода не должно получиться число с лидирующим нулем. Вам нужно определить минимальное количество ходов, которое требуется применить к числу, чтобы оно делилось на 6. Если получить число, делящееся на 6, невозможно, выведите -1. В числе может быть много цифр, но для удобства и во избежание работы со строковыми типами данных вам даны все цифры этого числа по одной в строке.

Формат ввода

В первой строке записано количество цифр в числе 1 ≤ m ≤ 103. В следующих m строках записаны цифры этого числа, по одной цифре в каждой строке, в порядке от старших разрядов к младшим. Гарантируется, что каждая цифра от 0 до 9 и первая цифра не равна 0(даже если число состоит из одной цифры).

Формат вывода

Выведите единственное число - минимальное количество операций, необходимых для того, чтобы получить число, делящееся на 6.Если получить число, делящееся на 6, невозможно, выведите -1.

Пример 1

Ввод Вывод

3

2

1

3

2

Пример 2

Ввод Вывод

3

1

2

2

-1