crap code

n, m = map(int, input().split())
a = list(map(int, input().split()))

di = {}
di2 = {}
l = []
for i in range(n):
    di[i+1] = (i,i,i)
    l += [i+1]
    di2[i] = i+1


for x in a:
    if di[x][2] == 0:
        continue
    else:
        di[x] = [min(di[x][0], di[x][2] - 1), di[x][1], di[x][2]-1]
        di[di2[di[x][2]]] = [di[di2[di[x][2]]][0], max(di[di2[di[x][2]]][2]+1, di[di2[di[x][2]]][1]), di[di2[di[x][2]]][2]+1]
        di2[di[x][2]], di2[di[x][2]+1] = di2[di[x][2]+1], di2[di[x][2]]

for p in di:
    print(di[p][0]+1, di[p][1]+1)