local N = io.read("n")
local P = {}
local sort_count = {}
sort_count[0] = 0
for i=1,N do
    P[i] = io.read("n")
    sort_count[i] = 0
end

for i=1,N do
    local n = P[i]
    sort_count[n] = sort_count[n-1] + 1
end

local max = 0
for i=1,N do
    if sort_count[i] > max then
        max = sort_count[i]
    end
end

print(N-max)
