Олимпиадный тренинг

Задача 31927. Subsequence


Задача

Темы: Остатки
Write a program that, in some sequence of integers, finds the subsequence of the smallest length whose sum of elements is a number ending in 6 or more zeros (divisible without remainder by 1000000).
The first input line contains one integer N (2 ≤ N ≤ 100000). The second input line contains N integers in the range from 1 to 109 separated by spaces.
Output two integers – the number of elements in the subsequence and the number of its first element. If there are several variants of such a subsequence with the smallest length, print the subsequence with the smallest number of the first element. If no such subsequence exists – print one number –1.

Enter Output
6
1 2 701000 299000 1000 999000
2 3
3
1 2 3
-1