R=range
J=lambda:list(map(int,input().split()))
N,*_=J()
P=J()
p=1
while N>p:p*=2
T=[N+1]*p*2
def S(i,u):
	j=p|i
	T[j],j=u,j>>1
	while j:T[j],j=min(T[j*2],T[j*2+1]),j>>1
def G(l,r):
	l|=p
	r+=p+1
	a=b=N+1
	while l<r:
		if l&1:a,l=min(a,T[l]),l+1
		if r&1:b,r=min(T[r-1],b),r-1
		l,r=l>>1,r>>1
	return min(a,b)
o=[0]*N
for i in R(N):
	l,r=-1,N-1
	while l+1<r:
		m=(l+r)>>1
		if G(m,N-1)<P[i]:l=m
		else:r=m
	o[i]=r;S(r,min(G(r,r),P[i]))
a=[]
for i,k in zip(R(N),o):
	while k>=len(a):a+=[[N,N]]
	a[k]=[min(a[k][0],i),min(a[k][1],P[i])]
for x,y in a:print(x+1,y)