Satellite Relay Sync Index

EasyArrayMathDigit sum2 sample tests5 hidden tests

A ground control network operates n satellite relays, numbered 0 through n-1 in the order they were commissioned. Each relay continuously broadcasts a diagnostic code, a single non-negative integer. Engineers call a relay "in sync" when the sum of the decimal digits of its diagnostic code exactly equals its own index in the network. Given the diagnostic codes of all n relays, report the smallest index of any in-sync relay. If no relay is in sync, report -1.

Input format

Line 1: a single integer n, the number of relays.
Line 2: n space-separated non-negative integers c_0, c_1, ..., c_{n-1}, the diagnostic code of each relay in index order.

Output format

A single integer: the smallest index i such that the digit sum of c_i equals i, or -1 if no such index exists.

Constraints

1 <= n <= 1000
0 <= c_i <= 10^9 for every relay

Examples

Example 1

Input

6
4 1000 1000000 1 0 15

Expected

Explanation

The diagnostic code at index 0 is 4, whose digit sum (4) does not equal 0. The code at index 1 is 1000, whose digit sum is 1+0+0+0=1, which equals the index 1, so relay 1 is the first (smallest) in-sync relay and the answer is 1.

Example 2

Input

3
1 2 3

Expected

-1

Explanation

Digit sums are 1, 2, 3 for indices 0, 1, 2 respectively; none matches its own index (1 does not equal 0, 2 does not equal 1, 3 does not equal 2), so no relay is in sync and the answer is -1.

Ready to solve this?