Problem: You are given a sequence D_1, D_2, ..., D_N of length N. The values of D_i are all distinct. Does a tree with N vertices that satisfies the following conditions exist?

* The vertices are numbered 1,2,..., N.
* The edges are numbered 1,2,..., N-1, and Edge i connects Vertex u_i and v_i.
* For each vertex i, the sum of the distances from i to the other vertices is D_i, assuming that the length of each edge is 1.



If such a tree exists, construct one such tree.

Constraints

* 2 \leq N \leq 100000
* 1 \leq D_i \leq 10^{12}
* D_i are all distinct.

Input

Input is given from Standard Input in the following format:


N
D_1
D_2
:
D_N


Output

If a tree with n vertices that satisfies the conditions does not exist, print `-1`.

If a tree with n vertices that satisfies the conditions exist, print n-1 lines. The i-th line should contain u_i and v_i with a space in between. If there are multiple trees that satisfy the conditions, any such tree will be accepted.

Examples

Input

7
10
15
13
18
11
14
19


Output

1 2
1 3
1 5
3 4
5 6
6 7


Input

2
1
2


Output

-1


Input

15
57
62
47
45
42
74
90
75
54
50
66
63
77
87
51


Output

1 10
1 11
2 8
2 15
3 5
3 9
4 5
4 10
5 15
6 12
6 14
7 13
9 12
11 13

Solution (in JAVA):

Solution:
import java.util.*;
import java.util.Map.Entry;
import java.util.stream.Collectors;

class Main {
    public static void main(String[] args) throws Exception {
        Map<Integer, Long> G = new HashMap<Integer, Long>();
        Map<Integer, Integer> V = new HashMap<Integer, Integer>();
        final Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Pair[] d = new Pair[N+1];
        int[] n = new int[N+1];
        long[] m = new long[N+1];
        int i = 0, flag = 0;
        for(i = 1 ; i <= N ; i++){
            G.put(i, sc.nextLong());
            n[i] = 1;
        }
        G = G.entrySet().stream()
        .sorted(Entry.<Integer, Long>comparingByValue().reversed())
        .collect(Collectors.toMap(Entry::getKey,Entry::getValue,(e1, e2)->e1,LinkedHashMap::new));
        i = 1;
        for (int key : G.keySet()){
            d[i] = new Pair(key, G.get(key));
            i++;
        }
        for(i = 1 ; i < N ; i++){
            flag = 0;
            for(int j = i+1 ; j <= N ; j++){
                if(d[i].b-(long)N+(long)(2*n[i]) == d[j].b){
                    n[j] += n[i];
                    m[j] += n[i]+m[i];
                    V.put(d[i].a, d[j].a);
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                System.out.println("-1");
                System.exit(0);
            }
        }
        if(m[N]!=d[N].b){
            System.out.println("-1");
            System.exit(0);
        }
        for (Integer key : V.keySet()) {
            System.out.println(key + " " + V.get(key));
        }
    }

    static class Pair implements Comparable<Pair> {
        int a;
        long b;
        Pair(int a,long b) {
            this.a = a;
            this.b = b;
        }    
        @Override
        public int compareTo(Pair o) {
            return Long.compare(a, o.b);
        }
    }
}