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 reg register
typedef long long ll;
using namespace std;
const int MN=1e5+5;
int n,fa[MN],siz[MN],id[MN];
ll d[MN];
inline bool cmp(int x,int y){return d[x]<d[y];}
map<ll,int>mp;
ll ans;
int h[MN],cnt,to[MN],nxt[MN];
inline void ins(int s,int t){
	to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;
}
void dfs(int st,int fa=0,int dep=0){
	ans+=dep;for(reg int i=h[st];i;i=nxt[i])dfs(to[i],st,dep+1);
}
int main(){
	ios::sync_with_stdio(false);cin>>n;
	for(reg int i=1;i<=n;i++)cin>>d[i],id[i]=i,siz[i]=1,mp[d[i]]=i;
	sort(id+1,id+1+n,cmp);reg int cnt=0;
	for(reg int i=n;i>1;i--){
		reg int pos=id[i];reg ll fad=d[pos]+2ll*siz[pos]-n;
		if(!mp[fad]||fad>=d[pos])return 0*puts("-1");
		reg int fap=mp[fad];siz[fap]+=siz[pos];ins(fap,pos);
	}
	dfs(id[1]);if(d[id[1]]^ans)return 0*puts("-1");
	for(reg int i=1;i<=n;i++)for(reg int j=h[i];j;j=nxt[j])printf("%d %d\n",i,to[j]);
	return 0;
}