import sys

import heapq

from operator import itemgetter

from collections import deque, defaultdict, Counter

from bisect import bisect_left, bisect_right

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7

INF = float('inf')



def sol():

    N = int(eval(input()))

    P = [0] * N



    for i in range(N):

        P[i] = int(eval(input()))



    pToIndex = {p : i for i, p in enumerate(P)}



    maxLeng = 1

    length = 1

    for n in range(1, N):

        if pToIndex[n] < pToIndex[n + 1]:

            length += 1

            maxLeng = max(maxLeng, length)

        else:

            length = 1



    print((N - maxLeng))



sol()
import sys

import heapq

from operator import itemgetter

from collections import deque, defaultdict, Counter

from bisect import bisect_left, bisect_right

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7

INF = float('inf')



def sol():

    N = int(eval(input()))

    P = [0] * N

    index = [0] * (N + 1)



    for i in range(N):

        P[i] = int(eval(input()))

        index[P[i]] = i



    length = 1

    seq = 1

    for i in range(1, N):

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

            seq += 1

        else:

            length = max(length, seq)

            seq = 1

            

    length = max(length, seq)



    print((N - length))



sol()

import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


def sol():
    N = int(eval(input()))
    P = [0] * N
    for i in range(N):
        P[i] = int(eval(input()))
    pToIndex = {p: i for i, p in enumerate(P)}
    maxLeng = 1
    length = 1
    for n in range(1, N):
        if pToIndex[n] < pToIndex[n + 1]:
            length += 1
            maxLeng = max(maxLeng, length)
        else:
            length = 1
    print((N - maxLeng))


sol()

import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


def sol():
    N = int(eval(input()))
    P = [0] * N
    index = [0] * (N + 1)
    for i in range(N):
        P[i] = int(eval(input()))
        index[P[i]] = i
    length = 1
    seq = 1
    for i in range(1, N):
        if index[i] < index[i + 1]:
            seq += 1
        else:
            length = max(length, seq)
            seq = 1
    length = max(length, seq)
    print((N - length))


sol()

+    index = [0] * (N + 1) -    pToIndex = {p: i for i, p in enumerate(P)} -    maxLeng = 1 +        index[P[i]] = i -    for n in range(1, N): -        if pToIndex[n] < pToIndex[n + 1]: -            length += 1 -            maxLeng = max(maxLeng, length) +    seq = 1 +    for i in range(1, N): +        if index[i] < index[i + 1]: +            seq += 1 -            length = 1 -    print((N - maxLeng)) +            length = max(length, seq) +            seq = 1 +    length = max(length, seq) +    print((N - length))