local n = io.read("*n")
local t = {}
for i = 1, n do t[i] = i end
for i = 1, n do
  local a = io.read("*n")
  t[a] = i
end
local f = {}
for i = 1, n - 1 do
  f[i] = t[i] < t[i + 1]
end
f[n] = false
local len = 0
local mma = math.max
local mlen = 0
for i = 1, n do
  if f[i] then
    len = len + 1
  else
    mlen = mma(mlen, len)
    len = 0
  end
end
print(n - 1 - mlen)
