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 <cstdio>
#include <algorithm>
using namespace std;

int N;
long long D[100010];
int cnt[100010];
int ansu[100010], ansv[100010];
int idx[100010];
long long Dv[100010];

int bsrch(int ll, int rr, long long vv)
{
	int l=ll, r=rr;
	int m;
	while(l<r){
		m = (l+r)/2;
		if(D[idx[m]] >= vv){
			r = m;
		}
		else
			l = m+1;
	}
	return l;
}

bool cmp(int aa, int bb)
{
	return D[aa] < D[bb];
}

int solve()
{
	int i, j=0;
	int ii;
	for(i=0; i<N; i++)
		idx[i] = i;
	sort(idx, idx+N, cmp);
	for(ii=N-1; ii>0; ii--){
		i = idx[ii];
		int p = bsrch(0, ii, D[i]-(N-2-cnt[i]*2) );
		if(p>=ii || D[idx[p]]!=D[i]-(N-2-cnt[i]*2) )
			return 0;
		cnt[idx[p]] += cnt[i]+1;
		Dv[idx[p]] += Dv[i] + (cnt[i]+1);
		ansu[j] = idx[p];
		ansv[j] = i;
		j ++;
	}
	if(Dv[idx[0]] != D[idx[0]])
		return 0;
	for(i=0; i<N-1; i++){
		printf("%d %d\n", ansu[i]+1, ansv[i]+1);
	}
	return 1;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int i;
	scanf("%d", &N);
	for(i=0; i<N; i++)
		scanf("%lld", &D[i]);
	if(solve() == 0)
		printf("-1\n");
	return 0;
}