1955. Кондукторы

Каждый день на линию одного из автобусных маршрутов выходит `K` (`1\ ≤\ K\ ≤\ 50`) машин, на каждой из которых работает кондуктор. Перед началом работы кондукторы получают по рулону автобусных билетов. Все билеты пронумерованы шестизначными числами. Каждый рулон состоит из 1000 билетов с номерами от ###000 до ###999, то есть три первых цифры номера билетов из одного рулона совпадают. Кондукторы получают рулоны с последовательными номерами билетов. Например, если первый кондуктор получает рулон с билетами 000000–000999, то второй получит рулон с билетами 001000–001999, третий 002000–002999 и так далее…

Получив рулон билетов, каждый кондуктор пересчитывает, сколько из них "счастливые". "Счастливым" считается билет, у которого сумма цифр, стоящих на чётных местах, совпадает с суммой цифр, стоящих на нечётных местах. Например, билет с номером 112233 является "счастливым" (`1+2+3=1+2+3`), а билет с номером 321213 — нет (`3+1+1≠2+2+3`).

Для каждого из `K` кондукторов известно, сколько счастливых билетов он насчитал в своём рулоне. Требуется определить, какие номера билетов в рулоне у первого кондуктора.

Первая строка входного файла содержит целое число `K` — число автобусов, вышедших на маршрут. Вторая строка содержит `K` целых чисел из диапазона `[0;\ 1000]`, разделённых пробелами — количество "счастливых" билетов у кондукторов: первого, второго, …, `K`-го.

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

3
75 75 73

4

4
28 36 45 55

30

1
0

-1