output_description: Print the minimum number of operations required.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      P_1
      :
      P_N
attempt: # -*- coding: utf-8 -*-
  
  #############
  # Libraries #
  #############
  
  import sys
  
  input = sys.stdin.readline
  
  import math
  
  # from math import gcd
  import bisect
  import heapq
  from collections import defaultdict
  from collections import deque
  from collections import Counter
  from functools import lru_cache
  
  #############
  # Constants #
  #############
  
  MOD = 10**9 + 7
  INF = float("inf")
  AZ = "abcdefghijklmnopqrstuvwxyz"
  
  #############
  # Functions #
  #############
  
  
  ######INPUT######
  def I():
      return int(input().strip())
  
  
  def S():
      return input().strip()
  
  
  def IL():
      return list(map(int, input().split()))
  
  
  def SL():
      return list(map(str, input().split()))
  
  
  def ILs(n):
      return list(int(input()) for _ in range(n))
  
  
  def SLs(n):
      return list(input().strip() for _ in range(n))
  
  
  def ILL(n):
      return [list(map(int, input().split())) for _ in range(n)]
  
  
  def SLL(n):
      return [list(map(str, input().split())) for _ in range(n)]
  
  
  ######OUTPUT######
  def P(arg):
      print(arg)
      return
  
  
  def Y():
      print("Yes")
      return
  
  
  def N():
      print("No")
      return
  
  
  def E():
      exit()
  
  
  def PE(arg):
      print(arg)
      exit()
  
  
  def YE():
      print("Yes")
      exit()
  
  
  def NE():
      print("No")
      exit()
  
  
  #####Shorten#####
  def DD(arg):
      return defaultdict(arg)
  
  
  #####Inverse#####
  def inv(n):
      return pow(n, MOD - 2, MOD)
  
  
  ######Combination######
  kaijo_memo = []
  
  
  def kaijo(n):
      if len(kaijo_memo) > n:
          return kaijo_memo[n]
      if len(kaijo_memo) == 0:
          kaijo_memo.append(1)
      while len(kaijo_memo) <= n:
          kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
      return kaijo_memo[n]
  
  
  gyaku_kaijo_memo = []
  
  
  def gyaku_kaijo(n):
      if len(gyaku_kaijo_memo) > n:
          return gyaku_kaijo_memo[n]
      if len(gyaku_kaijo_memo) == 0:
          gyaku_kaijo_memo.append(1)
      while len(gyaku_kaijo_memo) <= n:
          gyaku_kaijo_memo.append(
              gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD
          )
      return gyaku_kaijo_memo[n]
  
  
  def nCr(n, r):
      if n == r:
          return 1
      if n < r or r < 0:
          return 0
      ret = 1
      ret = ret * kaijo(n) % MOD
      ret = ret * gyaku_kaijo(r) % MOD
      ret = ret * gyaku_kaijo(n - r) % MOD
      return ret
  
  
  ######Factorization######
  def factorization(n):
      arr = []
      temp = n
      for i in range(2, int(-(-(n**0.5) // 1)) + 1):
          if temp % i == 0:
              cnt = 0
              while temp % i == 0:
                  cnt += 1
                  temp //= i
              arr.append([i, cnt])
      if temp != 1:
          arr.append([temp, 1])
      if arr == []:
          arr.append([n, 1])
      return arr
  
  
  #####MakeDivisors######
  def make_divisors(n):
      divisors = []
      for i in range(1, int(n**0.5) + 1):
          if n % i == 0:
              divisors.append(i)
              if i != n // i:
                  divisors.append(n // i)
      return divisors
  
  
  #####MakePrimes######
  def make_primes(N):
      max = int(math.sqrt(N))
      seachList = [i for i in range(2, N + 1)]
      primeNum = []
      while seachList[0] <= max:
          primeNum.append(seachList[0])
          tmp = seachList[0]
          seachList = [i for i in seachList if i % tmp != 0]
      primeNum.extend(seachList)
      return primeNum
  
  
  #####GCD#####
  def gcd(a, b):
      while b:
          a, b = b, a % b
      return a
  
  
  #####LCM#####
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  
  #####BitCount#####
  def count_bit(n):
      count = 0
      while n:
          n &= n - 1
          count += 1
      return count
  
  
  #####ChangeBase#####
  def base_10_to_n(X, n):
      if X // n:
          return base_10_to_n(X // n, n) + [X % n]
      return [X % n]
  
  
  def base_n_to_10(X, n):
      return sum(int(str(X)[-i - 1]) * n**i for i in range(len(str(X))))
  
  
  def base_10_to_n_without_0(X, n):
      X -= 1
      if X // n:
          return base_10_to_n_without_0(X // n, n) + [X % n]
      return [X % n]
  
  
  #####IntLog#####
  def int_log(n, a):
      count = 0
      while n >= a:
          n //= a
          count += 1
      return count
  
  
  #############
  # Main Code #
  #############
  N = I()
  A = ILs(N)
  
  START = []
  f = [0 for i in range(N + 1)]
  for a in A:
      if f[a - 1] == 0:
          START.append(a)
          f[a] = 1
      else:
          f[a] = 1
  START.sort()
  dic = {k: [] for k in START}
  for a in A:
      p = bisect.bisect(START, a)
      dic[START[p - 1]].append(a)
  print(N - max(len(dic[k]) for k in START))
  
problem_description: Statement
  
  You are given a sequence (P_1,P_2,...,P_N) which is a permutation of the
  integers from 1 through N. You would like to sort this sequence in ascending
  order by repeating the following operation:
  
    * Choose an element in the sequence and move it to the beginning or the end of the sequence.
  
  Find the minimum number of operations required. It can be proved that it is
  actually possible to sort the sequence using this operation.
samples: [{"input": "4\n    1\n    3\n    2\n    4", "output": "2\n    \n\nFor example, the sequence can be sorted in ascending order as follows:\n\n  * Move 2 to the beginning. The sequence is now (2,1,3,4).\n  * Move 1 to the beginning. The sequence is now (1,2,3,4).\n\n* * *"}, {"input": "6\n    3\n    2\n    5\n    1\n    4\n    6", "output": "4\n    \n\n* * *"}, {"input": "8\n    6\n    3\n    1\n    2\n    7\n    4\n    8\n    5", "output": "5"}]