n=int(eval(input()))

p=[int(eval(input())) for i in range(n)]

l=[-1 for i in range(n)]

for i in range(n):

  l[p[i]-1]=i

ans=[]

ct=1

for i in range(n-1):

  if l[i]<l[i+1]:

    ct+=1

  else:

    ans.append(ct)

    ct=1

ans.append(ct)

ct=1

print((n-max(ans)))
n=int(eval(input()))

p=[int(eval(input())) for i in range(n)]

dp=[0]*n

ans=0

for i in range(n):

  if p[i]!=1:

    dp[p[i]-1]=dp[p[i]-2]+1

  else:

    dp[0]=1

print((n-max(dp)))
n = int(eval(input()))
p = [int(eval(input())) for i in range(n)]
l = [-1 for i in range(n)]
for i in range(n):
    l[p[i] - 1] = i
ans = []
ct = 1
for i in range(n - 1):
    if l[i] < l[i + 1]:
        ct += 1
    else:
        ans.append(ct)
        ct = 1
ans.append(ct)
ct = 1
print((n - max(ans)))

n = int(eval(input()))
p = [int(eval(input())) for i in range(n)]
dp = [0] * n
ans = 0
for i in range(n):
    if p[i] != 1:
        dp[p[i] - 1] = dp[p[i] - 2] + 1
    else:
        dp[0] = 1
print((n - max(dp)))

-l = [-1 for i in range(n)] +dp = [0] * n +ans = 0 -    l[p[i] - 1] = i -ans = [] -ct = 1 -for i in range(n - 1): -    if l[i] < l[i + 1]: -        ct += 1 +    if p[i] != 1: +        dp[p[i] - 1] = dp[p[i] - 2] + 1 -        ans.append(ct) -        ct = 1 -ans.append(ct) -ct = 1 -print((n - max(ans))) +        dp[0] = 1 +print((n - max(dp)))