N = int(eval(input()))

A = [int(eval(input())) for i in range(N)]

Q =[0]*(N)

for i in range(N):

    Q[A[i]-1] = i+1

num = 1

ans = 1

for i in range(N-1):

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

        num += 1

    else:

        num = 1

    ans =max(ans,num)

print((N-ans))
import sys

input = sys.stdin.readline



N=int(eval(input()))

A=[int(eval(input()))-1 for i in range(N)]

Q=[0]*N

for i in range(N):

    Q[A[i]]= i

#print(Q)

num=0

s=1

t=Q[0]

for i in range(1,N):

    if t>Q[i]:

        num=max(s,num)

        s=0

    s+=1

    t=Q[i]

    #print(s)

num=max(s,num)

print((N-num))
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
Q = [0] * (N)
for i in range(N):
    Q[A[i] - 1] = i + 1
num = 1
ans = 1
for i in range(N - 1):
    if Q[i] < Q[i + 1]:
        num += 1
    else:
        num = 1
    ans = max(ans, num)
print((N - ans))

import sys

input = sys.stdin.readline
N = int(eval(input()))
A = [int(eval(input())) - 1 for i in range(N)]
Q = [0] * N
for i in range(N):
    Q[A[i]] = i
# print(Q)
num = 0
s = 1
t = Q[0]
for i in range(1, N):
    if t > Q[i]:
        num = max(s, num)
        s = 0
    s += 1
    t = Q[i]
    # print(s)
num = max(s, num)
print((N - num))

+import sys + +input = sys.stdin.readline -A = [int(eval(input())) for i in range(N)] -Q = [0] * (N) +A = [int(eval(input())) - 1 for i in range(N)] +Q = [0] * N -    Q[A[i] - 1] = i + 1 -num = 1 -ans = 1 -for i in range(N - 1): -    if Q[i] < Q[i + 1]: -        num += 1 -    else: -        num = 1 -    ans = max(ans, num) -print((N - ans)) +    Q[A[i]] = i +# print(Q) +num = 0 +s = 1 +t = Q[0] +for i in range(1, N): +    if t > Q[i]: +        num = max(s, num) +        s = 0 +    s += 1 +    t = Q[i] +    # print(s) +num = max(s, num) +print((N - num))