N = int(eval(input()))

idx = {int(eval(input())): i for i in range(N)}

res = N - 1

cnt = 1

for x in range(2, N + 1):

    if idx[x - 1] < idx[x]:

        cnt += 1

    else:

        res = min(res, N - cnt)

        cnt = 1

print((min(res, N - cnt)))
import sys

N = int(eval(input()))

dp = [0] * (N + 1)

for x in map(int, sys.stdin):

    dp[x] = dp[x - 1] + 1

print((N - max(dp)))
N = int(eval(input()))
idx = {int(eval(input())): i for i in range(N)}
res = N - 1
cnt = 1
for x in range(2, N + 1):
    if idx[x - 1] < idx[x]:
        cnt += 1
    else:
        res = min(res, N - cnt)
        cnt = 1
print((min(res, N - cnt)))

import sys

N = int(eval(input()))
dp = [0] * (N + 1)
for x in map(int, sys.stdin):
    dp[x] = dp[x - 1] + 1
print((N - max(dp)))

+import sys + -idx = {int(eval(input())): i for i in range(N)} -res = N - 1 -cnt = 1 -for x in range(2, N + 1): -    if idx[x - 1] < idx[x]: -        cnt += 1 -    else: -        res = min(res, N - cnt) -        cnt = 1 -print((min(res, N - cnt))) +dp = [0] * (N + 1) +for x in map(int, sys.stdin): +    dp[x] = dp[x - 1] + 1 +print((N - max(dp)))