Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

E. Candies Game

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIahub is playing an uncommon game. Initially, he has *n* boxes, numbered 1, 2, 3, ..., *n*. Each box has some number of candies in it, described by a sequence *a*_{1}, *a*_{2}, ..., *a*_{n}. The number *a*_{k} represents the number of candies in box *k*.

The goal of the game is to move all candies into exactly two boxes. The rest of *n* - 2 boxes must contain zero candies. Iahub is allowed to do several (possible zero) moves. At each move he chooses two different boxes *i* and *j*, such that *a*_{i} ≤ *a*_{j}. Then, Iahub moves from box *j* to box *i* exactly *a*_{i} candies. Obviously, when two boxes have equal number of candies, box number *j* becomes empty.

Your task is to give him a set of moves such as Iahub to archive the goal of the game. If Iahub can't win the game for the given configuration of boxes, output -1. Please note that in case there exist a solution, you don't need to print the solution using minimal number of moves.

Input

The first line of the input contains integer *n* (3 ≤ *n* ≤ 1000). The next line contains *n* non-negative integers: *a*_{1}, *a*_{2}, ..., *a*_{n} — sequence elements. It is guaranteed that sum of all numbers in sequence *a* is up to 10^{6}.

Output

In case there exists no solution, output -1. Otherwise, in the first line output integer *c* (0 ≤ *c* ≤ 10^{6}), representing number of moves in your solution. Each of the next *c* lines should contain two integers *i* and *j* (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*): integers *i*, *j* in the *k*th line mean that at the *k*-th move you will move candies from the *j*-th box to the *i*-th one.

Examples

Input

3

3 6 9

Output

2

2 3

1 3

Input

3

0 1 0

Output

-1

Input

4

0 1 1 0

Output

0

Note

For the first sample, after the first move the boxes will contain 3, 12 and 3 candies. After the second move, the boxes will contain 6, 12 and 0 candies. Now all candies are in exactly 2 boxes.

For the second sample, you can observe that the given configuration is not valid, as all candies are in a single box and they should be in two boxes. Also, any move won't change the configuration, so there exists no solution.

For the third sample, all candies are already in 2 boxes. Hence, no move is needed.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 12:54:05 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|