Каждый день на линию одного из автобусных
маршрутов выходит 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
|
