import sys

input = sys.stdin.readline

import heapq





def read():

    N = int(input().strip())

    P = []

    for i in range(N):

        p = int(input().strip())

        P.append(p)

    return N, P





def solve(N, P):

    h = []

    for i in range(N):

        heapq.heappush(h, (P[i], i+1))

    max_count = 0

    count = 0

    prev = -1

    for _ in range(N):

        p, i = heapq.heappop(h)

        if prev < i:

            count += 1

            prev = i

        else:

            max_count = max(max_count, count)

            count = 1

            prev = i

    max_count = max(max_count, count)

    return N - max_count





if __name__ == '__main__':

    inputs = read()

    print(("%s" % solve(*inputs)))

import sys

input = sys.stdin.readline

import heapq





def read():

    N = int(input().strip())

    P = []

    for i in range(N):

        p = int(input().strip())

        P.append(p)

    return N, P





def solve(N, P):

    Q = [0 for i in range(N)]

    for i in range(N):

        Q[P[i]-1] = i

    max_count = 0

    count = 0

    prev = -1

    for i in range(N):

        q = Q[i]

        if prev < q:

            count += 1

            prev = q

        else:

            max_count = max(max_count, count)

            count = 1

            prev = q

    max_count = max(max_count, count)

    return N - max_count





if __name__ == '__main__':

    inputs = read()

    print(("%s" % solve(*inputs)))

import sys

input = sys.stdin.readline
import heapq


def read():
    N = int(input().strip())
    P = []
    for i in range(N):
        p = int(input().strip())
        P.append(p)
    return N, P


def solve(N, P):
    h = []
    for i in range(N):
        heapq.heappush(h, (P[i], i + 1))
    max_count = 0
    count = 0
    prev = -1
    for _ in range(N):
        p, i = heapq.heappop(h)
        if prev < i:
            count += 1
            prev = i
        else:
            max_count = max(max_count, count)
            count = 1
            prev = i
    max_count = max(max_count, count)
    return N - max_count


if __name__ == "__main__":
    inputs = read()
    print(("%s" % solve(*inputs)))

import sys

input = sys.stdin.readline
import heapq


def read():
    N = int(input().strip())
    P = []
    for i in range(N):
        p = int(input().strip())
        P.append(p)
    return N, P


def solve(N, P):
    Q = [0 for i in range(N)]
    for i in range(N):
        Q[P[i] - 1] = i
    max_count = 0
    count = 0
    prev = -1
    for i in range(N):
        q = Q[i]
        if prev < q:
            count += 1
            prev = q
        else:
            max_count = max(max_count, count)
            count = 1
            prev = q
    max_count = max(max_count, count)
    return N - max_count


if __name__ == "__main__":
    inputs = read()
    print(("%s" % solve(*inputs)))

-    h = [] +    Q = [0 for i in range(N)] -        heapq.heappush(h, (P[i], i + 1)) +        Q[P[i] - 1] = i -    for _ in range(N): -        p, i = heapq.heappop(h) -        if prev < i: +    for i in range(N): +        q = Q[i] +        if prev < q: -            prev = i +            prev = q -            prev = i +            prev = q