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 CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<ll,int>    ii;

ii  a[N];
int s[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    for(int i = 1 ; i <= n ; ++i)   {
        ll  x;  cin >> x;
        a[i].X = x;
        a[i].Y = i;
    }
    sort(a + 1,a + 1 + n);
    fill(s + 1,s + 1 + n,1);

    vector<ii>  res;

    ll  Sum = 0;

    for(int i = n ; i >= 2 ; --i)   {
        ll  val = a[i].X + s[i] + s[i] - n;
        int pos = lower_bound(a + 1,a + 1 + n,ii(val,0)) - a;

        if (a[pos].X != val)    {
            cout << "-1";
            return  0;
        }
        s[pos] += s[i]; res.pb(a[pos].Y,a[i].Y);
        Sum += s[i];
    }
    if (Sum != a[1].X)  {
        cout << "-1";
        return  0;
    }
    for(ii  e : res)
        cout << e.X << " ",
        cout << e.Y << "\n";
}