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 |