Программирование Последовательность чисел

Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, которое при делении на число 112 дает в остатке число 4. Программа на вход получается количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, которое при делении на число 112 дает в остатке 4.

Количество чисел не превышает 1000. Введенные числа не превышают 30 000. Программа должна вывести одно число: максимальное число, которое при делении на число 112 дает в остатке 4.

Пример работы программы:

Входные данные	Выходные данные
5 112 4 113 114 224	4