An infinitely long railway has a train consisting of n cars, numbered from 1 to n (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of cars in the train. 

The second line contains n integers p_{i} (1 ≤ p_{i} ≤ n, p_{i} ≠ p_{j} if i ≠ j) — the sequence of the numbers of the cars in the train.


-----Output-----

Print a single integer — the minimum number of actions needed to sort the railway cars.


-----Examples-----
Input
5
4 1 2 5 3

Output
2

Input
4
4 1 3 2

Output
2



-----Note-----

In the first sample you need first to teleport the 4-th car, and then the 5-th car to the end of the train.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
arr = map(int, input().split())
li = [0] * (n + 1)
for i in arr:
	li[i] = li[i - 1] + 1
print(n - max(li))


a = [0 for i in range(100010)]
b = [0 for i in range(100010)]
c = [0 for i in range(100010)]
(n, a[1:]) = (int(input()), map(int, input().split(' ')))
for i in range(1, n + 1):
	if b[a[i] - 1]:
		c[a[i]] = c[a[i] - 1] + 1
	else:
		c[a[i]] = 1
	b[a[i]] = 1
print(n - max(c[1:n + 1]))


def li(kkk, n):
	lis = [0] * (n + 1)
	lis[0] = 0
	for i in range(0, n):
		lis[kkk[i]] = lis[kkk[i] - 1] + 1
	return max(lis)
n = int(input())
kkk = list(map(int, input().split()))
ans = li(kkk, n)
print(n - ans)


n = int(input())
a = list(map(int, input().split()))
pos = [0] * (n + 1)
for i in range(n):
	pos[a[i]] = i
cnt = 1
ans = 1
for i in range(2, n + 1):
	if pos[i] > pos[i - 1]:
		cnt += 1
	else:
		if cnt > ans:
			ans = cnt
		cnt = 1
if cnt > ans:
	ans = cnt
print(n - ans)


n = int(input())
l = [n] * (n + 1)
for c in map(int, input().split()):
	l[c] = l[c - 1] - 1
print(min(l))


import sys
lines = sys.stdin.readlines()
N = int(lines[0])
a = list(map(int, lines[1].split(' ')))
b = [-1 for _ in a]
for (i, x) in enumerate(a):
	b[x - 1] = i
cur_len = max_len = 1
for i in range(1, N):
	if b[i - 1] < b[i]:
		cur_len += 1
	else:
		cur_len = 1
	if cur_len > max_len:
		max_len = cur_len
print(N - max_len)


n = int(input().strip())
p = [int(x) for x in input().split()]
l = {}
for x in p:
	if x - 1 in l:
		l[x] = l[x - 1] + 1
	else:
		l[x] = 1
print(n - max(l.values()))


n = int(input())
p = list(map(int, input().split()))
dp = [0] * (n + 1)
for x in p:
	dp[x] = 1 + dp[x - 1]
res = n - max(dp)
print(res)


n = int(input())
a = list(map(int, input().split()))
dp = [0] * (n + 1)
for i in a:
	dp[i] = dp[i - 1] + 1
ans = n - max(dp)
dp = [0] * (n + 2)
for i in range(n - 1, -1, -1):
	dp[a[i]] = dp[a[i] + 1] + 1
ans = min(ans, n - max(dp))
print(ans)


def main():
	n = int(input())
	l = [n] * (n + 1)
	for a in map(int, input().split()):
		l[a] = l[a - 1] - 1
	print(min(l))

def __starting_point():
	main()
__starting_point()


import collections, itertools, functools, math

def solve():
	n = int(input())
	p = list(map(int, input().split()))
	pos = [(p, i) for (i, p) in enumerate(p)]
	pos.sort()
	longest = 1
	seq = 1
	for i in range(1, n):
		if pos[i - 1][1] < pos[i][1]:
			seq += 1
		else:
			seq = 1
		longest = max(longest, seq)
	return n - longest

def __starting_point():
	print(solve())
__starting_point()


readInts = lambda : list(map(int, input().split()))
n = int(input())
a = readInts()
p = [0] * n
for i in range(n):
	p[a[i] - 1] = i
inc = 1
ret = n - 1
for i in range(1, n):
	if p[i] > p[i - 1]:
		inc += 1
	else:
		inc = 1
	ret = min(ret, n - inc)
print(ret)


__author__ = 'Utena'
n = int(input())
m = list(map(int, input().split()))
t = 0
l = [0]
r = [0] * (n + 1)
for j in range(n):
	r[m[j]] = j + 1
if n == 1:
	print(0)
else:
	for i in range(1, n):
		t += 1
		if r[i] > r[i + 1]:
			l.append(t)
			t = 0
	if r[n] > r[n - 1]:
		t += 1
		l.append(t)
	print(n - max(l))


n = int(input())
p = [int(i) for i in input().split()]
(b, result) = ([0] * (n + 1), 0)
for i in range(n):
	b[p[i]] = b[p[i] - 1] + 1
	result = max(result, b[p[i]])
print(n - result)


import time
n = int(input())
p = [int(i) for i in input().split()]
d = {}
start = time.time()
for i in range(n):
	d[p[i]] = i
l = 0
i = 2
while i <= n:
	j = 0
	while i <= n and d[i] > d[i - 1]:
		i += 1
		j += 1
	if j > l:
		l = j
	i += 1
print(n - l - 1)
finish = time.time()


q = int(input())
w = list(map(int, input().split()))
e = [0] * (q + 1)
r = 1
l = 0
for i in range(q):
	e[w[i]] = i
for i in range(2, q + 1):
	if e[i] > e[i - 1]:
		r += 1
	else:
		r = 1
	l = max(r, l)
if q == 1:
	print(0)
else:
	print(q - l)


n = int(input())
arr = [int(x) for x in input().split()]
d = {}
for i in range(n):
	if arr[i] - 1 in d:
		d[arr[i]] = d[arr[i] - 1] + 1
	else:
		d[arr[i]] = 1
print(n - max(d.values()))


n = int(input())
Arr = [int(i) for i in input().split()]
L = [0] * (n + 1)
ans = 0
for i in range(n):
	if L[Arr[i] - 1] == 0:
		L[Arr[i]] = 1
	else:
		L[Arr[i]] = 1 + L[Arr[i] - 1]
	ans = max(ans, L[Arr[i]])
print(n - ans)


n = int(input())
cars = [int(x) for x in input().split()]
sorted_cars = sorted(enumerate(cars), key=lambda x: x[1])
max_sorted_length = 1
length = 1
for i in range(1, n):
	if sorted_cars[i][0] > sorted_cars[i - 1][0]:
		length += 1
	else:
		if max_sorted_length < length:
			max_sorted_length = length
		length = 1
if max_sorted_length < length:
	max_sorted_length = length
print(n - max_sorted_length)


from math import *
from collections import Counter, defaultdict
from sys import stdin, stdout
input = stdin.readline
I = lambda : int(input())
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
for _ in range(1):
	n = I()
	a = LI()
	b = [0] * n
	for i in range(n):
		b[a[i] - 1] = i
	(c, d) = (1, 1)
	for i in range(1, n):
		if b[i - 1] < b[i]:
			c += 1
		else:
			c = 1
		d = max(d, c)
	print(n - d)


n = int(input())
p = list(map(int, input().split()))
cur = set()
d = [1] * (n + 1)
for i in p:
	if i in cur:
		d[i] = max(d[i], d[i - 1] + 1)
	cur.add(i + 1)
ans = n - max(d)
print(ans)


n = int(input())
list = [int(x) for x in input().split(' ')]
key_position_dict = {x: i for (i, x) in enumerate(list)}
list = [key_position_dict[x] for x in range(1, n + 1)]
len = 1
maxi = 1
for i in range(1, n):
	if list[i - 1] < list[i]:
		len += 1
	else:
		len = 1
	maxi = max(len, maxi)
print(n - maxi)


3
N = int(input())
l = [1 for x in range(N + 1)]
m = [1 for x in range(N + 1)]
usr_input = input().split()
ans = 1
for x in range(N):
	m[int(usr_input[x])] = x + 1
for x in range(2, N + 1):
	if m[x] > m[x - 1]:
		l[x] += l[x - 1]
	if l[x] > ans:
		ans = l[x]
print(N - ans)


dl = int(input())
vag = list(map(int, input().split()))
pl = [0] * (dl + 1)
for i in range(dl):
	pl[vag[i] - 1] = i
dmax = 0
d = 1
for i in range(1, dl):
	if pl[i] > pl[i - 1]:
		d = d + 1
	else:
		if d > dmax:
			dmax = d
		d = 1
if d > dmax:
	dmax = d
print(dl - dmax)


(n, arr) = (int(input()), list(map(int, input().split())))
a = [0] * (max(arr) + 5)
for i in arr:
	a[i] = a[i - 1] + 1
print(n - max(a))


import sys
input = sys.stdin.readline
n = int(input())
p = list(map(int, input().split()))
dp = [-1] * n
for pi in p:
	pi -= 1
	if pi == 0:
		dp[pi] = 1
	elif dp[pi - 1] != -1:
		dp[pi] = dp[pi - 1] + 1
	else:
		dp[pi] = 1
ans = min((n - dp[i] for i in range(n)))
print(ans)


n = int(input())
a = list(map(int, input().split()))
r = [0] + [0] * n
for i in range(n):
	r[a[i]] = i + 1
count = 1
maxcount = 1
for i in range(2, n + 1):
	if r[i] > r[i - 1]:
		count += 1
	else:
		if count > maxcount:
			maxcount = count
		count = 1
if count > maxcount:
	maxcount = count
print(n - maxcount)


def answer(n, A):
	dp = [0] * (n + 1)
	for i in range(0, n):
		dp[A[i]] = dp[A[i] - 1] + 1
	return n - max(dp)
n = int(input())
arr = list(map(int, input().split()))
print(answer(n, arr))


n = int(input())
v = list(map(int, input().split()))
uns = dict()
for i in range(n):
	uns[i + 1] = -1
for i in range(n):
	if v[i] != 1 and uns[v[i] - 1] != -1:
		uns[v[i]] = uns[v[i] - 1] + 1
	else:
		uns[v[i]] = 1
print(n - max(uns.values()))


def train(p):
	m = 0
	s = {}
	for pi in p:
		k = s.get(pi - 1, 0) + 1
		s[pi] = k
		m = max(k, m)
	return len(p) - m
n = int(input())
p = list(map(int, input().split()))
print(train(p))


n = int(input())
p = list(map(int, input().split()))
for i in range(n):
	p[i] = [p[i], i]
p.sort()
b = 1
d = []
for i in range(n - 1):
	if p[i][1] < p[i + 1][1]:
		b += 1
	else:
		d.append(b)
		b = 1
d.append(b)
print(n - max(d))


n = int(input())
line = map(int, input().split())
book = [0] * n
for it in line:
	if it > 1:
		if book[it - 2] > 0:
			book[it - 1] = book[it - 2] + 1
		else:
			book[it - 1] = 1
	else:
		book[it - 1] = 1
print(n - max(book))


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	(n,) = aj()
	A = aj()
	pos = {A[i]: i for i in range(n)}
	ans = n - 1
	prev = -1
	c = 0
	for i in range(1, n + 1):
		if pos[i] > prev:
			c += 1
		else:
			c = 1
		prev = pos[i]
		ans = min(ans, n - c)
	print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


n = int(input())
p = list(map(int, input().split()))
d = {}
for i in p:
	d[i] = d.get(i - 1, 0) + 1
maxi = max(d.values())
print(n - maxi)


from sys import stdin
input = stdin.readline
n = int(input())
p = list(map(int, input().split()))
idx = [0] * (n + 1)
for i in range(n):
	idx[p[i]] = i
cnt = 1
ans = 10 ** 18
for i in range(1, n):
	if idx[i] < idx[i + 1]:
		cnt += 1
	else:
		ans = min(ans, n - cnt)
		cnt = 1
ans = min(ans, n - cnt)
print(ans)


n = int(input())
a = list(map(int, input().split()))
mp = [0] * (n + 1)
for i in range(n):
	mp[a[i]] = i + 1
cnt = 0
mx = 1
for i in range(1, n):
	if mp[i] < mp[i + 1]:
		cnt += 1
	else:
		mx = max(mx, cnt + 1)
		cnt = 0
mx = max(mx, cnt + 1)
print(n - mx)


n = int(input())
lis = [0] * (n + 1)
res = 0
for s in input().split(' '):
	lis[int(s)] = lis[int(s) - 1] + 1
	res = max(res, lis[int(s)])
print(n - res)


n = int(input())
seq = list(map(int, input().split(' ')))
a = [0] * (len(seq) + 1)
result = 1
a[seq[0]] = 1
for i in range(1, len(seq)):
	if a[seq[i] - 1]:
		a[seq[i]] = a[seq[i] - 1] + 1
		result = max(result, a[seq[i]])
	else:
		a[seq[i]] = 1
print(len(seq) - result)


n = int(input())
p = [0] * (n + 1)
lista = list(map(int, input().split()))
for i in lista:
	p[i] = p[i - 1] + 1
x = max(p)
print(n - x)


from __future__ import print_function
from itertools import permutations as perm
from functools import cmp_to_key
from fractions import Fraction
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = gil()
dp = [1] * n
ans = 1
idx = [-1] * (n + 2)
for i in reversed(range(n)):
	v = a[i]
	idx[v] = i
	if idx[v + 1] != -1:
		dp[i] += dp[idx[v + 1]]
		ans = max(ans, dp[i])
print(n - ans)


n = int(input())
a = input().split()
pos = {}
ans = {}
num = 0
for i in range(n):
	a[i] = int(a[i])
	pos.setdefault(a[i], num)
	num += 1
	ans.setdefault(a[i], 1)
num = 0
for i in reversed(a):
	if i == n:
		continue
	if pos[i + 1] > pos[i]:
		ans[i] += ans[i + 1]
print(n - max(ans.values()))


n = int(input())
lst = [0 for i in range(n)]
kereta = input().split()
for i in range(n):
	lst[int(kereta[i]) - 1] = i
ancol = 1
terbanyak = 0
for i in range(n - 1):
	if lst[i] > lst[i + 1]:
		if terbanyak < ancol:
			terbanyak = ancol
		ancol = 0
	ancol += 1
if terbanyak < ancol:
	terbanyak = ancol
print(n - terbanyak)


n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
res = 0
for i in a:
	b[i] = b[i - 1] + 1
	res = max(res, b[i])
print(n - res)


n = int(input())
m = [0] * (n + 1)
l = list(map(int, input().split()))
for i in l:
	m[i] = m[i - 1] + 1
print(n - max(m))


n = int(input())
l = list(map(int, input().split()))
a = [0] * (n + 1)
k = 0
for x in l:
	a[x] = a[x - 1] + 1
	k = max(k, a[x])
print(n - k)


n = int(input())
p = [0] + [int(a) for a in input().split()]
loc = [0] * (n + 1)
for i in range(n):
	loc[p[i + 1]] = i + 1
best = 0
run = 1
for i in range(2, n + 1):
	if loc[i] > loc[i - 1]:
		run += 1
	else:
		best = max(run, best)
		run = 1
best = max(run, best)
print(n - best)


N = 100000 + 77
n = int(input())
a = list(map(int, input().split()))
T = [0] * N
A = 0
for i in a:
	T[i] = T[i - 1] + 1
	A = max(A, T[i])
print(n - A)


def LIS(s):
	n = len(s)
	L = [0] * n
	appear = [False] * n
	L[0] = 1
	find = [-1] * n
	appear[s[0]] = True
	find[s[0]] = 0
	for i in range(1, len(s)):
		if s[i] > 0 and appear[s[i] - 1]:
			L[i] = L[find[s[i] - 1]] + 1
		else:
			L[i] = 1
		appear[s[i]] = True
		find[s[i]] = i
	return max(L)

def BIS(s):
	n = len(s)
	L = [0] * n
	appear = [False] * n
	L[n - 1] = 1
	find = [-1] * n
	appear[s[n - 1]] = True
	find[s[n - 1]] = n - 1
	for i in range(n - 2, -1, -1):
		if s[i] + 1 < n and appear[s[i] + 1]:
			L[i] = L[find[s[i] - 1]] + 1
		else:
			L[i] = 1
		appear[s[i]] = True
		find[s[i]] = i
	return max(L)
n = int(input())
L = list(map(int, input().split()))
L = [x - 1 for x in L]
print(n - max(LIS(L), BIS(L)))


(n, p) = (int(input()), list(map(int, input().split())))
(a, c, v) = ([0] * n, 1, 1)
for (i, pi) in enumerate(p):
	a[pi - 1] = i
for i in range(n - 1):
	if a[i] < a[i + 1]:
		c += 1
		if c > v:
			v = c
	else:
		c = 1
print(n - v)


import sys, os, io
from sys import stdin
from collections import defaultdict
from bisect import bisect_left, bisect_right

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = ii()
l = li()
d = defaultdict(lambda : -1)
m = [0] * (n + 1)
for i in range(n):
	m[l[i]] = 1
	if d[l[i] - 1] != -1 and d[l[i] - 1] < i:
		m[l[i]] += m[l[i] - 1]
	d[l[i]] = i
print(n - max(m))


n = int(input())
arr = list(map(int, input().split()))
l = [0] * (n + 1)
for c in arr:
	l[c] = l[c - 1] + 1
print(n - max(l))


n = int(input())
p = list(map(int, input().split()))
q = [0] * n
for i in range(n):
	q[p[i] - 1] = i
ans = 1
cur = 1
for i in range(1, n):
	if q[i - 1] < q[i]:
		cur += 1
	else:
		cur = 1
	ans = max(ans, cur)
print(n - ans)


n = int(input())
a = [int(v) for v in input().split()]
p = [0] * (n + 1)
for j in range(n):
	p[a[j]] = j + 1
c = 1
t = 1
for j in range(2, n + 1):
	if p[j] < p[j - 1]:
		c = max(c, t)
		t = 1
	else:
		t = t + 1
c = max(c, t)
print(n - c)


n = int(input())
l = list(map(int, input().split()))
l2 = [0] * len(l)
for i in range(len(l)):
	l2[l[i] - 1] = i
prev = -1
ans = -1000000000.0
curr = 0
for i in l2:
	if i > prev:
		curr += 1
		prev = i
	else:
		ans = max(curr, ans)
		curr = 1
	prev = i
print(n - max(curr, ans))


n = int(input())
l = [int(x) for x in input().split()]
b = [0] * (n + 1)
for i in l:
	b[i] = b[i - 1] + 1
print(n - max(b))


n = int(input())
u = list(map(int, input().split()))
l = [0] * (n + 2)
for i in range(n):
	l[u[i]] = i + 1
r = 0
a = 0
for i in range(1, n + 1):
	r += 1
	if l[i] > l[i + 1]:
		a = max(a, r)
		r = 0
print(n - a)


import sys
import math
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split(' ')))
maxsf = 1
idxs = {ai: i + 1 for (i, ai) in enumerate(a)}
i = 1
while i <= n:
	acc = 1
	while i < n and idxs[i + 1] > idxs[i]:
		acc += 1
		maxsf = max(maxsf, acc)
		i += 1
	i += 1
print(n - maxsf)


n = int(input())
p = [int(i) for i in input().split()]
store = [0] * (n + 1)
for i in range(len(p)):
	store[p[i]] = i + 1
store = store[1:]
(max_, cnt) = (0, 1)
for i in range(1, len(store)):
	if store[i] > store[i - 1]:
		cnt += 1
	else:
		cnt = 1
	max_ = max(max_, cnt)
if n == 1:
	print(0)
else:
	print(n - max_)


n = int(input())
a = list(map(int, input().split()))
d = [0] * (len(a) + 1)
q = [0] * (len(a) + 1)
m = 0
l = -1
for i in range(len(a)):
	d[a[i]] = i
for i in range(len(a)):
	q[i] = 1
	if a[i] != 1:
		q[i] = max(q[i], q[d[a[i] - 1]] + 1)
	m = max(m, q[i])
print(n - m)


n = int(input())
p = list(map(int, input().split()))
idx = [None] * (n + 1)
for (i, x) in enumerate(p):
	idx[x] = i
maxi = 1
l = 1
for i in range(1, n):
	if idx[i] < idx[i + 1]:
		l += 1
		if l > maxi:
			maxi = l
	else:
		l = 1
print(n - maxi)


n = int(input())
l = list(map(int, input().split()))
d = {}
ma = 0
for x in l:
	d[x] = d.get(x - 1, 0) + 1
	ma = max(ma, d[x])
print(n - ma)


import unittest
import sys

class Sort:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.n] = map(int, uinput().split())
		self.nums = list(map(int, uinput().split()))
		tr = [0] * self.n
		for i in range(self.n):
			tr[self.nums[i] - 1] = i
		max_len = 1
		for i in range(self.n):
			if i > 0 and tr[i] > tr[i - 1]:
				cur_len += 1
				max_len = max(max_len, cur_len)
			else:
				cur_len = 1
		self.result = self.n - max_len

	def calculate(self):
		return str(self.result)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '5\n4 1 2 5 3'
		d = Sort(test)
		self.assertEqual(d.n, 5)
		self.assertEqual(d.nums, [4, 1, 2, 5, 3])
		self.assertEqual(Sort(test).calculate(), '2')
		test = '4\n4 1 3 2'
		self.assertEqual(Sort(test).calculate(), '2')
		test = '8\n6 2 1 8 5 7 3 4'
		self.assertEqual(Sort(test).calculate(), '5')
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Sort(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Sort().calculate())


n = int(input())
l1 = list(map(int, input().split()))
l2 = [-1] * n
if n <= 1:
	print(0)
	exit()
for i in range(n):
	l2[l1[i] - 1] = i
ans = 0
cur = 1
for i in range(1, n):
	if l2[i] > l2[i - 1]:
		cur += 1
	else:
		cur = 1
	ans = max(ans, cur)
print(n - ans)


n = int(input())
p = list(map(int, input().split()))
dp = [1]
d = {i: 0 for i in range(1, n + 1)}
d[p[0]] = 1
for i in range(1, n):
	if p[i] == 1:
		dp.append(dp[i - 1])
		d[p[i]] = 1
	elif d[p[i] - 1] == 0:
		dp.append(dp[i - 1])
		d[p[i]] = 1
	elif d[p[i] - 1] + 1 > dp[i - 1]:
		dp.append(d[p[i] - 1] + 1)
		d[p[i]] = d[p[i] - 1] + 1
	else:
		dp.append(dp[i - 1])
		d[p[i]] = d[p[i] - 1] + 1
print(n - dp[n - 1])


read = lambda : map(int, input().split())
n = int(input())
p = list(read())
cur = set()
d = [1] * (n + 1)
for i in range(n):
	if p[i] in cur:
		cur.remove(p[i])
		d[p[i]] = max(d[p[i]], d[p[i] - 1] + 1)
	cur.add(p[i] + 1)
ans = n - max(d)
print(ans)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	indices = sorted(range(len(arr)), key=arr.__getitem__)
	largestSequenc = 1
	localSequence = 1
	for x in range(1, n):
		if indices[x] > indices[x - 1]:
			localSequence += 1
		else:
			largestSequenc = max(largestSequenc, localSequence)
			localSequence = 1
	largestSequenc = max(largestSequenc, localSequence)
	print(n - largestSequenc)
try:
	solve()
except Exception as e:
	print(e)


n = int(input())
ai = list(map(int, input().split()))
ar = [0] * (n + 1)
ans = 0
num = 0
for i in range(n):
	ar[ai[i]] = 1 + ar[ai[i] - 1]
print(n - max(ar))


n = int(input())
L = input().split()
IDX = (n + 2) * [0]

def max(a, b):
	if a > b:
		return a
	return b
(mx, act, last) = (0, 0, 0)
for i in range(n):
	IDX[int(L[i])] = i + 1
for i in range(1, n + 1):
	if IDX[i] > last:
		last = IDX[i]
		act += 1
	else:
		last = IDX[i]
		act = 1
	mx = max(mx, act)
print(n - mx)


n = int(input())
a = [int(i) for i in input().split()]
pos = [0 for i in range(n)]
for i in range(len(a)):
	pos[a[i] - 1] = i
m = 1
c = 1
for i in range(1, len(pos)):
	if pos[i] >= pos[i - 1]:
		c += 1
	else:
		m = max(m, c)
		c = 1
m = max(m, c)
print(n - m)


n = int(input())
v = [int(i) for i in input().split()]
f = [0] * (n + 1)
for i in range(n):
	f[v[i]] = f[v[i] - 1] + 1
print(n - max(f))


n = int(input())
ps = list(map(int, input().split()))
pos = [0] * n
for (i, p) in enumerate(ps):
	pos[p - 1] = i
used = [False] * n
longest = 0
for v in range(n):
	if used[v]:
		continue
	i = pos[v]
	w = v
	used[w] = True
	while w < n - 1 and pos[w + 1] > i:
		i = pos[w + 1]
		w += 1
		used[w] = True
	longest = max(longest, w - v + 1)
print(n - longest)


__author__ = 'MoonBall'
import sys
T = 1

def process():
	N = int(input())
	a = list(map(int, input().split()))
	d = [0] * (N + 1)
	for _a in a:
		d[_a] = d[_a - 1] + 1
	print(N - max(d))
for _ in range(T):
	process()


n = int(input())
l = [n] * (n + 1)
for c in [int(x) for x in input().split()]:
	l[c] = l[c - 1] - 1
print(min(l))


n = int(input())
vagons = tuple(map(int, input().split()))
res = [0] * n
places = [0] * (n + 1)
for i in range(n):
	places[vagons[i]] = i
for i in range(n - 1, -1, -1):
	v = vagons[i]
	if v < n:
		res[i] = res[places[v + 1]] + 1
	else:
		res[i] = 1
print(n - max(res))


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(test,) = Neo()
n = test
A = Neo()
s = set()
B = [1] * (n + 1)
for i in A:
	if i - 1 in s:
		B[i] += B[i - 1]
	s.add(i)
print(n - max(B))


def lengthOfLIS(nums):
	d = {}
	for num in nums:
		if num - 1 in d:
			d[num] = d[num - 1] + 1
		else:
			d[num] = 1
	return max(d.values())
n = int(input())
a = list(map(int, input().split()))
print(n - lengthOfLIS(a))