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>
#define rep(X,A,B) for(int X=A;X<=B;X++)
#define tep(X,A,B) for(int X=A;X>=B;X--)
#define LL long long
#define DB double
const int N=400010;
const int M=800010;
using namespace std;

int n;
map<LL,int> mp;
LL sz[N];
int fa[N],edge[M],lst[N],nxt[M],t=0;

struct nn{
	LL d;
	int id;
}a[N];

int cmp(nn A,nn B){
	return A.d<B.d;
}

void READ(){
	scanf("%d",&n);
	rep(i,1,n)scanf("%lld",&a[i].d),a[i].id=i,mp[a[i].d]=i;
	sort(a+1,a+n+1,cmp);
}

void ADD(int x,int y){
	edge[++t]=y;nxt[t]=lst[x];lst[x]=t;
}

LL SEARCH(int x,int dep){
	LL res=dep;
	for(int r=lst[x];r;r=nxt[r]){
		res+=SEARCH(edge[r],dep+1);
	}
	return res;
}

int SOLVE(){
	rep(i,1,n)sz[i]=1;
	tep(i,n,2){
		int x=a[i].id;
		LL d=a[i].d;
		LL now=d+2*sz[x]-n;
		int pos=mp[now];
		if(pos==0||now>=a[i].d)return 0;
		fa[x]=pos;
		ADD(fa[x],x);
		sz[fa[x]]+=sz[x];
	}
	LL sum=SEARCH(a[1].id,0);
	if(sum!=a[1].d)return 0;
	rep(i,1,n){
		if(i==a[1].id)continue;
		printf("%d %d\n",i,fa[i]);
	}
	return 1;
}

int main(){
	READ();
	if(!SOLVE())printf("-1\n");
	return 0;
}