N=int(input())
P=list(map(int,input().split()))

ans_x=[]
ans_y=[]
B=[]
from bisect import *

for i in range(N):
    bi=bisect_left(B,P[i])
    if (bi==len(B)):
        B.append(P[i])
        ans_x.append(10**9)
        ans_y.append(10**9)
    else:
        B[bi]=P[i]
    ans_x[bi]=min(ans_x[bi],i+1)
    ans_y[bi]=min(ans_y[bi],P[i])

for i in range(len(B)):
    print(ans_x[i],ans_y[i])