N = int(input())

P = []

for i in range(N):

	P.append(int(input()))



Q = list(range(N))



for i in range(N):

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



count = 0

max = 0

for i in range(N-1):

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

		count+=1

	else:

		count=0

	

	if max < count:

		max = count



print(N-max-1)
import sys

def input():

    return sys.stdin.readline()[:-1]



N = int(eval(input()))



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



T = [0]*(N-1)



E = [0]*N



for i in range(N):

    E[P[i]-1] = 1

    if P[i]<N:

        if E[P[i]]==1:

            T[P[i]-1] = 1



max_score = 0

prev = -1



for i in range(N-1):

    if T[i]==1:

        max_score=max(max_score,i-prev)

        prev = i



max_score = max(max_score,N-1-prev)



print((N-max_score))
N = int(input())
P = []
for i in range(N):
    P.append(int(input()))
Q = list(range(N))
for i in range(N):
    Q[P[i] - 1] = i + 1
count = 0
max = 0
for i in range(N - 1):
    if Q[i] < Q[i + 1]:
        count += 1
    else:
        count = 0
    if max < count:
        max = count
print(N - max - 1)

import sys


def input():
    return sys.stdin.readline()[:-1]


N = int(eval(input()))
P = [int(eval(input())) for i in range(N)]
T = [0] * (N - 1)
E = [0] * N
for i in range(N):
    E[P[i] - 1] = 1
    if P[i] < N:
        if E[P[i]] == 1:
            T[P[i] - 1] = 1
max_score = 0
prev = -1
for i in range(N - 1):
    if T[i] == 1:
        max_score = max(max_score, i - prev)
        prev = i
max_score = max(max_score, N - 1 - prev)
print((N - max_score))

-N = int(input()) -P = [] +import sys + + +def input(): +    return sys.stdin.readline()[:-1] + + +N = int(eval(input())) +P = [int(eval(input())) for i in range(N)] +T = [0] * (N - 1) +E = [0] * N -    P.append(int(input())) -Q = list(range(N)) -for i in range(N): -    Q[P[i] - 1] = i + 1 -count = 0 -max = 0 +    E[P[i] - 1] = 1 +    if P[i] < N: +        if E[P[i]] == 1: +            T[P[i] - 1] = 1 +max_score = 0 +prev = -1 -    if Q[i] < Q[i + 1]: -        count += 1 -    else: -        count = 0 -    if max < count: -        max = count -print(N - max - 1) +    if T[i] == 1: +        max_score = max(max_score, i - prev) +        prev = i +max_score = max(max_score, N - 1 - prev) +print((N - max_score))