Программирование. Кратность

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

В последовательности всегда имеется число, которое при делении на число 112 даёт в остатке 4.

Количество чисел не превышает 1000. Введённые числа не превышают 30 000.

Программа должна вывести одно число: максимальное число, которое при делении на число 112 даёт в остатке 4.