Problem:
 Score : 500 points    Problem 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.      Constraints  1 \leq N \leq 2\times 10^5  (P_1,P_2,...,P_N) is a permutation of (1,2,...,N) .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  P_1  :  P_N       Output Print the minimum number of operations required.        Sample Input 1 4
1
3
2
4      Sample Output 1 2  For example, the sequence can be sorted in ascending order as follows:   Move 2 to the beginning. The sequence is now (2,1,3,4) .  Move 1 to the beginning. The sequence is now (1,2,3,4) .        Sample Input 2 6
3
2
5
1
4
6      Sample Output 2 4       Sample Input 3 8
6
3
1
2
7
4
8
5      Sample Output 3 5

Solution (Python):
import sys

n = int(sys.stdin.readline())
p = [None] * n
for i in range(n):
    p[i] = int(sys.stdin.readline())
a = [None] * n
for i in range(n):
    a[p[i]-1] = i
prv = -1
mx = 1
nw = 0
for i in range(n):
    if prv < a[i]:
        nw += 1
        mx = max(mx, nw)
    else:
        nw = 1
    prv = a[i]
print(n-mx)

Solution (Python):
import sys

n = int(sys.stdin.readline())
p = [int(sys.stdin.readline()) for i in range(n)]
a = [None] * n
for i in range(n):
    a[p[i]-1] = i
prv = -1
mx = 1
nw = 0
for i in range(n):
    if prv < a[i]:
        nw += 1
        mx = max(mx, nw)
    else:
        nw = 1
    prv = a[i]
print(n-mx)

Solution (Python):
import sys

n = int(sys.stdin.readline())
p = [int(sys.stdin.readline()) for i in range(n)]
a = [0] * n
for i in range(n):
    a[p[i]-1] = i
prv = -1
mx = 1
nw = 0
for i in range(n):
    if prv < a[i]:
        nw += 1
        mx = max(mx, nw)
    else:
        nw = 1
    prv = a[i]
print(n-mx)

Solution (Python):
n = int(input())
p = [int(input()) for i in range(n)]
a = [0] * n
for i in range(n):
    a[p[i]-1] = i
prv = -1
mx = 1
nw = 0
for i in range(n):
    if prv < a[i]:
        nw += 1
        mx = max(mx, nw)
    else:
        nw = 1
    prv = a[i]
print(n-mx)

Solution (Python):
n=int(input())
a=[0]*n
for _ in range(n):
	a[int(input())-1]=_

k=1
ans=1
for i in range(n-1):
	if a[i]<a[i+1]:
		k+=1
	else:
		ans=max(ans,k)
		k=1
print(n-max(ans,k))

Solution (Python):

n = int(input())
p = [int(input())for i in range(n)]

a = [n+1] * (n+1)
b = []
k = 1

for i in range(0,n):
    a[p[i]] = i
    
for i in range(1,n+1):
    if a[i] > a[i-1]:
        k += 1
    else:
        b.append(k)
        k = 1
    if i == n:
        b.append(k)

print(n-max(b))

Solution (Python):
n = int(input())
p = [int(input()) for i in range(n)]
q = [0]*(n+1)
for i in range(n):
  q[p[i]] = i
cnt = 1
m = 1
for i in range(1, n):
  if q[i]<q[i+1]:
    cnt += 1
    m = max(m, cnt)
  else:
    cnt = 1
print(n-m)

Solution (Python):
def main():
    n = int(input())
    dp = [-1 for _ in range(n)]
    for _ in range(n):
        x = int(input()) - 1
        if x > 0 and dp[x - 1] != -1:
            dp[x] = dp[x - 1] + 1
        else:
            dp[x] = 1
    print(n - max(dp))

main()

Solution (Python):
N = int(input())
P = []
Q = [0 for i in range(N+1)]
for i in range(1, N+1):
    Q[int(input())] = i

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)

Solution (Python):
n = int(input())
list = [int(input()) for _ in range(n)]

link = [0] * ( n + 1)
for i in range(n):
    link[ list[i]] = link[list[i] -1] + 1
print( n - max(link))

Solution (Python):
N = int(input())
temp = [0 for x in range(N+1)]






for i in range(N):
  X=int(input())
  temp[X]=temp[X-1]+1
  
print(N-max(temp))

Solution (Python):
N = int(input())
temp = [0 for x in range(N+1)]



for i in range(N):
    num = int(input())
    temp[num] = 0
    temp[num] = temp[num-1]+1
    temp[num-1] = 0

print(N-max(temp))

Solution (Python):


import sys, math, copy





HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(input())
    an = [int(input()) for i in range(n)]
    assert len(an) == n
    sublen = [0 for i in range(n + 1)]
    for i in range(n):
        a1 = an[i]
        sublen[a1] = sublen[a1 - 1] + 1
    res = max(sublen)
    print(n - res)

main()

Solution (Python):
import sys
from sys import stdin, stdout

rem=10**9+7
sys.setrecursionlimit(10 ** 6)
take = lambda: map(int, stdin.readline().split())

n=input()
ans=[1 for i in range(n+1)]
pos={}
for i in range(1,n+1):
    x=take()[0]
    pos[x]=i
for i in range(n-1,0,-1):
    if pos[i]<pos[i+1]:
        ans[i]=ans[i+1]+1

print n-max(ans)

Solution (Python):
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
d = {}
for i in range(len(a)):
    if a[i] - 1 in d:
        v = d[a[i] - 1]
        del d[a[i] - 1]
        d[a[i]] = v + 1
    else:
        d[a[i]] = 1
print(len(a) - max(list(d.values())))

Solution (Python):
n = int(input())
p = [int(input()) for _ in range(n)]

indeces = [0] * n

for i in range(n):
	indeces[p[i] - 1] = i

ans = 0
pre_ans = 0

for i in range(n - 1):
	if indeces[i] < indeces[i + 1]:
		pre_ans += 1
	else:
		if pre_ans > ans:
			ans = pre_ans
		pre_ans = 0

if pre_ans > ans:
	ans = pre_ans

print(n - ans - 1)

Solution (Python):
import numpy as np

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


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


N = ii()
P = []
for _ in range(N):
    p = ii()
    P.append(p-1)

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

maxcnt = 1
cnt = 1
for i in range(1, N):
    if Q[i] > Q[i-1]:
        cnt += 1
    else:
        cnt = 1

    maxcnt = max(maxcnt, cnt)

print(N - maxcnt)

Solution (Python):
n = int(input())
t = [0]*n
for i in range(n):
    p = int(input())-1
    t[p] = i
maxi = 1
c = 1
for i in range(n-1):
  a = t[i]
  b = t[1+i]
  if a < b:
    c += 1
  else:
    maxi = max(c,maxi)
    c = 1
maxi = max(c,maxi)
print(n - maxi)

Solution (Python):
n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=0
num=0
n_th = 0
s={}
for i in p:
	if i-1 in s:
		s[i]=s[i-1]+1
	else:
		s[i]=1
print(n-max(s.values()))

Solution (Python):
n = int(input())
l = [ int(input().rstrip()) for i in range(n)]

s = {}
for i in l:
    if i - 1 in s:
        s[i] = s[i - 1] + 1
        del s[i - 1]
    else:
            s[i] = 1
print(n - max(s.values()))

Solution (Python):
def main():
    n = int(input())
    l = [ int(input().rstrip()) for i in range(n)]

    s = {}
    for i in l:
        if i - 1 in s:
            s[i] = s[i - 1] + 1
            del s[i - 1]
        else:
            s[i] = 1
    print(n - max(s.values()))

if __name__ == '__main__':
    main()

Solution (Python):
N = input()
P = []
for i in xrange(N):
	P.append(input())
Q = {}
for i in xrange(N):
	Q[P[i]-1]=i
longest_length = 0
length_of_sequence = 1
for i in xrange(N-1):
	if Q[i+1] > Q[i]:
		length_of_sequence += 1
	else:
		longest_length = max(longest_length, length_of_sequence)
		length_of_sequence = 1
longest_length = max(longest_length, length_of_sequence)
print N - longest_length

Solution (Python):
N = int(raw_input())
P = []
for i in range(N):
	P.append(int(raw_input()))

Q = range(N)

for i in range(N):
	Q[P[i]-1] = i+1

count = 0
max = 0
for i in range(N-1):
	if Q[i]<Q[i+1]:
		count+=1
	else:
		count=0
	
	if max < count:
		max = count

print N-max-1

Solution (Python):
import numpy as np

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


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


N = ii()
P = []
for _ in range(N):
    p = ii()
    P.append(p-1)

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

maxcnt = 1
cnt = 1
for i in range(1, N):
    if Q[i] > Q[i-1]:
        cnt += 1
    else:
        cnt = 1

    maxcnt = max(maxcnt, cnt)

print(N - maxcnt)

Solution (Python):
N = int(input())
dp = [None for _ in range(N)]
for i in range(N):
  p = int(input())
  if dp[p - 2] == None or p == 1:
    dp[p - 1] = 1
  else:
    dp[p - 1] = dp[p - 2] + 1
print(N - max(dp))

Solution (Python):
N = int(input())
a = [0]
for _ in range(N):
  a.append(int(input()))

Q = [0 for i in range(N + 1)]
for i in range(N + 1):
    Q[a[i]] = i
ans = 1
num = 1

for idx in range(2, len(Q)):
    if Q[idx - 1] < Q[idx]:
        num += 1
    else:
        ans, num = max(num, ans), 1

print(N - max(num, ans))

Solution (Python):
n = int(input())
p = [int(input()) for i in range(n)]
x,r,num,ans = [0 for i in range(n)],0,1,0
for i in range(n): x[p[i]-1] = i
while r!=n-1:
	r += 1
	if x[r-1]<x[r]: num = num+1
	else: ans,num = max(ans,num),1
ans = max(ans,num)
print(n-ans)

Solution (Python):


n=int(raw_input())
p=[]
for i in xrange(n):
 p.append(int(raw_input()))
r=[0]*(n+1)
for x in p:
 r[x]=r[x-1]+1
print n-max(r)

Solution (Python):
N = int(raw_input())
P = [int(raw_input()) for _ in range(N)]
T = [0]*(N+1)
for p in P:
  T[p] = T[p-1]+1
print N-max(T)

Solution (Python):
n = int(input())
p = [int(input()) for _ in range(n)]
q = [0] * (n+1)

for i in range(n):
    q[p[i]] = i
maxl = 1
cnt = 1
for i in range(1, n):
    if q[i+1] > q[i]:
        cnt += 1
    else:
        maxl = max(maxl, cnt)
        cnt = 1
print(n - max(maxl, cnt))

Solution (Python):
N=int(input())
P=[int(input())-1 for i in range(N)]
Q=[0 for i in range(N)]
for i in range(N):
    Q[P[i]]=i
L=[1]
k=0
for i in range(1,N):
    if Q[i-1]<Q[i]:
        L[k]+=1
    else:
        L.append(0)
        k+=1
        L[k]+=1
print(N-max(L))

Solution (Python):

class Backfront:
    max_to_min = {}

    def add(self, x):
        if x - 1 in self.max_to_min:
            self.max_to_min[x] = self.max_to_min[x - 1]
            del self.max_to_min[x - 1]
        else:
            self.max_to_min[x] = x

    def longest_seq(self):
        return 1 + max([y - x for (y, x) in self.max_to_min.items()])

def main():
    n = int(input())

    backfront = Backfront()
    for _ in range(n):
        x = int(input())
        backfront.add(x)

    print("{0:d}".format(n - backfront.longest_seq()))

main()

Solution (Python):
n = int(input())

p = []
for i in range(n):
    p.append(int(input()))


q = [0 for i in range(n)]
for i in range(n):
    q[p[i] - 1] = i

result = 1
temp = 1
for i in range(1, n):
    if q[i] < q[i-1]:
        if temp > result:
            result = temp
        temp = 1
    else:
        temp += 1

if temp == n:
    result = temp

print(n - result)

Solution (Python):
N = int(input())
p = [int(input()) for i in range(N)]
q = [0]*N
for i in range(N):
  q[p[i]-1] = i

cnt = 1
max_cnt = 1
for i in range(N-1):
    if q[i+1] > q[i]:
        cnt += 1
    else:
        max_cnt = max(max_cnt, cnt)
        cnt = 1
max_cnt = max(max_cnt, cnt)
print(N - max_cnt)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    d = {}
    d[0] = -1
    for i in range(n):
        d[I()] = i
    r = n - 1
    c = 0
    for i in range(1,n+1):
        if d[i-1] > d[i]:
            if r > n - c:
                r = n - c
            c = 1
        else:
            c += 1
    if r > n - c:
        r = n - c

    return r




print(main())

Solution (Python):

"""
Contents   : AtCoder Grand Contest 024 B問題 WA
Author     : Kitaura Hiromi
LastUpdate : 20180520
Since      : 20180520
"""
N = int(input())
p = [int(input()) for i in range(N)]
q = [0 for i in range(N)]
for i in range(N):
    q[p[i]-1] = i

cnt = 1
max_cnt = 1
for i in range(N-1):
    if q[i+1] > q[i]:
        cnt += 1
    else:
        max_cnt = max(max_cnt, cnt)
        cnt = 1
max_cnt = max(max_cnt, cnt)
print(N - max_cnt)

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
Q = [0 for i in range(N+1)]
res = 100000000000000
for i in range(N):
	Q[P[i]] = Q[P[i] - 1] + 1
	res = min(res, N-Q[P[i]])
	
print(res)

Solution (Python):
N=int(input())
P=[int(input()) for _ in range(N)]
Q=[0 for _ in range(N)]

for i in range(N):
    Q[P[i]-1]=i

cnt=0
tmp=0
for i in range(N-1):
    if Q[i]<Q[i+1]:
        cnt+=1
    else:
        if tmp<cnt+1:
            tmp=cnt+1
        cnt=0

if tmp==0:
    tmp=cnt+1

print(N-tmp)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
Q =[0]*(N)
for i in range(N):
    Q[A[i]-1] = i+1
num = 1
ans = 1
for i in range(N-1):
    if Q[i]<Q[i+1]:
        num += 1
    else:
        num = 1
    ans =max(ans,num)
print(N-ans)

Solution (Python):
n = int(input())

p = [int(input()) for _ in range(n)]




lengths = {}
for pn in p:
    if pn in lengths:
        lengths[pn+1] = lengths[pn] + 1
    else:
        lengths[pn+1] = 1
    
max_count = max(lengths.values())
print(n-max_count)

Solution (Python):

"""
Created on Sun May 20 20:55:50 2018
AGC024B
@author: maezawa
"""

n = int(input())
q = [None for _ in range(n)]
for i in range(n):
    p = int(input())
    q[p-1] = i+1

max_cnt = 0
cnt = 1
qpre = q[0]
 
for i in range(1,n):
    if q[i] > qpre:
        cnt += 1
    else:
        if max_cnt < cnt:
            max_cnt = cnt
        cnt = 1
    qpre = q[i]
if max_cnt < cnt:
    max_cnt = cnt

print(n-max_cnt)

Solution (Python):
N = int(input())
P = []
for i in range(N):
    P.append(int(input()))

d = [0]*(N+1)
for p in P:
    d[p] = d[p-1]+1

print(N-max(d))

Solution (Python):
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


@mt
def slv(N, P):
    Q = [-1] * N
    for i, p in enumerate(P):
        Q[p - 1] = i

    p = -1
    mc = 0
    c = 0
    for q in Q:
        if q > p:
            c += 1
        else:
            c = 1
        mc = max(mc, c)
        p = q

    return N - mc


def main():
    N = read_int()
    P = [read_int() for _ in range(N)]

    print(slv(N, P))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

LCIS = [0 for i in range(N+1)]
for i in range(N):
    A = int(input())
    LCIS[A] = LCIS[A-1] + 1

print(N - max(LCIS))

Solution (Python):
N = int(input())
n_list_idx = [0 for _ in range(N + 1)]
for i in range(N):
    v = int(input())
    n_list_idx[v] = i

o_max = 1
o = 1
for i in range(2, len(n_list_idx)):
    if n_list_idx[i] > n_list_idx[i - 1]:
        o += 1
    else:
        if o > o_max:
            o_max = o
        o = 1
if o > o_max:
    o_max = o
print(N - o_max)

Solution (Python):

def main():
    N = int(input())
    P = [int(input()) for _ in [0] * N]

    num = [[j, i] for i, j in enumerate(P)]
    num.sort()
    cnt, maxcnt = 1, 1
    for i in range(N - 1):
        if num[i][1] < num[i+1][1]:
            cnt += 1
            maxcnt = max(maxcnt, cnt)
        else:
            cnt = 1
    print(N - maxcnt)

main()

Solution (Python):
N = int(input())
P = sorted([(int(input()), i) for i in range(N)])

cnt = 1
M = 1
for i in range(1, N):
    if P[i-1][1] < P[i][1]:
        cnt += 1
        M = max(M, cnt)
    else:
        M = max(M, cnt)
        cnt = 1

print(N-M)

Solution (Python):

def main():
    N = int(input())
    P = [int(input()) for _ in [0] * N]

    num = []
    apnd = num.append
    for i, j in enumerate(P):
        apnd([j, i])
    num.sort()

    cnt = 1
    maxcnt = 1
    for i in range(N - 1):
        if num[i][1] < num[i+1][1]:
            cnt += 1
            maxcnt = max(maxcnt, cnt)
        else:
            cnt = 1
    print(N - maxcnt)

main()

Solution (Python):
n = int(input())
p_list = [int(input()) for _ in range(n)]

q_dict = {0:0}
for i in range(n):
    q_dict[p_list[i]] = i
length = 0
ans = 1
for i in range(1, n+1):
    if q_dict[i] > q_dict[i-1]:
        length += 1
        if length > ans:
            ans = length
    else:
        length = 1
print(n - ans)

Solution (Python):
def main():
    N = int(input())
    P = [int(input()) for _ in range(N)]

    
    editorial(N, P)


def editorial(N, P):
    """
    入力例3
        N=8
        P=63127485
         |6   7 8 |
         | 3   4 5|
         |  12    |
        上記の3つの列は要素ai+1=aiである部分列
            連続する列が長いほど、移動しなくて済む要素は多い
            連続するためには、最小未満は左・最大より大きいものは末尾に移動する
        部分列(wikipediaより)
            残った要素がもとの数列における相対的な序列を保つ
            与えられた列からいくつかの要素を取り去ることによって得られる列
    ksomemo様にお借りしました
    """
    if N == 1:
        print(0)
        return

    
    a = [0] * (N+1)
    for i, p in enumerate(P):
        a[p] = i

    tmp = 1
    max_len = 1
    for i in range(1, N):
        if a[i] < a[i+1]:
            tmp += 1
            max_len = max(max_len, tmp)
        else:
            tmp = 1
    ans = N - max_len
    print(ans)


def WA(N, P):
    tmp = 0
    ans = 0
    for i, p in enumerate(P):
        if i == 0 or P[i-1] + 1 == p:
            tmp += 1
        else:
            ans = max(ans, tmp)
            tmp = 1

    print(N - ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    P = [int(input()) for _ in range(N)]

    
    editorial(N, P)


def editorial(N, P):
    """
    入力例3
        N=8
        P=63127485
         |6   7 8 |
         | 3   4 5|
         |  12    |
        上記の3つの列は要素ai+1=aiである部分列
            連続する列が長いほど、移動しなくて済む要素は多い
            連続するためには、最小未満は左・最大より大きいものは末尾に移動する
        部分列(wikipediaより)
            残った要素がもとの数列における相対的な序列を保つ
            与えられた列からいくつかの要素を取り去ることによって得られる列
    """
    if N == 1:
        print(0)
        return

    
    a = [0] * (N+1)
    for i, p in enumerate(P):
        a[p] = i

    tmp = 1
    max_len = 1
    for i in range(1, N):
        if a[i] < a[i+1]:
            tmp += 1
            max_len = max(max_len, tmp)
        else:
            tmp = 1

    ans = N - max_len
    print(ans)


def WA(N, P):
    tmp = 0
    ans = 0
    for i, p in enumerate(P):
        if i == 0 or P[i-1] + 1 == p:
            tmp += 1
        else:
            ans = max(ans, tmp)
            tmp = 1

    print(N - ans)


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
P=[None]*(N+1)
for i in range(1,N+1):
    P[i]=int(input())



Q=[0]*(N+2)

for i in range(1,N+1):
    Q[P[i]]=i

count=0
Ans=0
for i in range(1,N+2):
    if Q[i]>Q[i-1]:
        count+=1
    else:
        Ans=max(count,Ans)
        count=1

print(N-Ans)

Solution (Python):
N = int(input())
Q = [0]*N
for i in range(N):
        Q[int(input())-1] = i

subset_num = num = 0
for i in range(N-1):
    num += 1
    if Q[i] > Q[i+1]:
        subset_num = max(subset_num, num)
        num = 0
else:
    num += 1   
    subset_num = max(subset_num, num)
print(N - subset_num)

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
Q = [0]*N
for i in range(N):
    Q[P[i]-1] = i

count = 0
check = 0
maxlen = 0
for i in Q:
    if check < i:
        count += 1
        check = i
    else:
        maxlen = max(count, maxlen)
        count = 1
        check = i
maxlen = max(count, maxlen)
print(N-maxlen)

Solution (Python):
N = int(input())
Q = [0]*N
for i in range(N):
        Q[int(input())-1] = i

num = 0
ansr = 0
for i in range(N-1):
        if Q[i]<Q[i+1]:
                num += 1
        else:
                ansr = max(ansr,num)
                num = 0
if num == N-1:
        ansr = N-1
print(N-1-ansr)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
p=[]
q=[0 for i in range(n)]
for i in range(n):   
 p.append(i1())
 q[p[-1]-1]=i
k=1
s=0
for i in range(n-1):
  if q[i+1]-q[i]>0:
     k+=1
  else:
     s=max(s,k)
     k=1
s=max(s,k)
print(n-s)

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
K = [0]*(N+1)
for p in P:
    K[p] = K[p-1] + 1
print(N - max(K))

Solution (Python):
n = int(input())
ppp = list(map(int, (input() for _ in range(n))))

tmp = [0] * (n + 1)
for p in ppp:
    tmp[p] = tmp[p - 1] + 1

print(n - max(tmp))

Solution (Python):



import math
import sys
import itertools
import numpy as np

n =int(input())
t = [int(input()) for i in range(n)] 

a = [0]*(n)
for i in range(n):
    a[t[i]-1]=i
lmax =1
length=1

for i in range(1,n):
    if a[i] < a[i-1]:
        length = 1
    else:
        length += 1
        lmax = max(lmax,length)

print(n - lmax)

Solution (Python):
N = int(input())

Qs = [0 for _ in range(N)]
for i in range(N):
    tmp = int(input())
    Qs[tmp - 1] = i - 1

result, tmp = 1, 1
for i in range(N - 1):
    if Qs[i] < Qs[i + 1]:
        tmp += 1
    else:
        result = max(result, tmp)
        tmp = 1

print(N - max(result, tmp))

Solution (Python):
N = int(input())
a = [0]*N
cnt = 0
dic = {}
for i in range(N):
	a[i] = int(input())
	dic[a[i]] = i

ans = 1
cnt = 1
for num in range(1,N):
	if dic[num] < dic[num+1]:
		cnt += 1
	else:
		ans = max(cnt,ans)
		cnt = 1


ans = max(cnt,ans)
print(N-ans)

Solution (Python):
n=int(input())
p=[int(input())-1for _ in[0]*n]
q=[0]*n
for i in range(n):q[p[i]]=i
r,c=0,1
for i in range(n-1):
    c=c+1if q[i]<q[i+1]else 1
    if r<c:r=c
if r<c:r=c
print(n-r)

Solution (Python):
n = int(input())
p = [0 for i in range(n)]
for i in range(n):
    p[i] = int(input())

visited = [0 for i in range(n+1)]

"""
for i in reversed(range(n)):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1

        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
"""
for i in range(n):
    visited[p[i]] = visited[p[i] - 1] + 1
print(n - max(visited))

Solution (Python):
def main():
    N = int(input())
    P = [0 for _ in range(N)]
    for i in range(N):
        P[i] = int(input())
    C = [1,1]
    Q = [0 for _ in range(N)]
    for i in range(N):
        Q[P[i]-1] = i
    for i in range(1,N):
        if Q[i-1]<Q[i]:
            C[0]+=1
            C[1] = max(C[1], C[0])
        else:
            C[0] = 1
    print(N-C[1])

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
p = [int(input()) for i in range(n)]
tl = 1
n2i = [-1 for i in range(n)]
for i in range(n):
    n2i[p[i]-1] = i
tmp = 1
for i in range(n-1):
    if n2i[i] < n2i[i+1]:
        tmp += 1
    else:
        tmp = 1
    tl = max(tl, tmp)

ans = n - tl
print(ans)

Solution (Python):
import sys
if __name__ == "__main__":
    N = int(input())
    P = []
    Q = [0]*(N+1)
    for i in range(1, N+1):
        p = int(input())
        Q[p] = i

    
    
    
    cur = 1
    max_cur = 1
    for i in range(1, N):
        if Q[i] < Q[i+1]:
            cur += 1
            max_cur = max(cur, max_cur)
        else:
            cur = 1
    print(N - max_cur)

Solution (Python):
N = input()
P = [input() for _ in range(N)]
T = [0]*(N+1)
for p in P:
  T[p] = T[p-1]+1
print N-max(T)

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
 
al= {}
ans=0
for ai in a:
  if ai - 1 in al.keys():
    al[ai]=al[ai-1]+1
    ans=max(ans,al[ai-1]+1)   
    del al[ai-1]
  else:
    al[ai]=0

print(n-ans-1)

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]

check = [0] * N

for i in P:
    if check[i-1] == 0:
        if (i-2 >= 0 and check[i-2] == 0) or i == 1:
            check[i-1] = 1
        else:
            check[i-1] = 2
count = 0
ans = 0
for i in range(N):
    if check[i] == 2:
        count += 1
    else:
        ans = max(ans, count)
        count = 1
ans = max(ans, count)

print(N-ans)

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]

al= {}
ans=0
for ai in a:
  if ai - 1 in al.keys():
    al[ai]=al[ai-1]+1
    ans=max(ans,al[ai-1]+1)   
    del al[ai-1]
  else:
    al[ai]=0
    if ai + 1 in al.keys():
      del al[ai]
print(n-ans-1)

Solution (Python):
n = int(input())
nums = [int(input()) for _ in range(n)]
mem = [0] * (n + 1)
a, b = 1, 1
s = 0
for i in range(n):
    mem[nums[i]] += i

p, q = mem[1], mem[n]

for i in range(2, n+1):
    if  p < mem[i]:
        a += 1
    else:
        s = max(s, a)
        a = 1
    p = mem[i]
s = max(s, a)
for j in range(n, 0, -1):
    if  q > mem[j]:
        b += 1
    else:
        s = max(s, b)
        b = 1
    q = mem[j]
s = max(s, b)
print(n - s)

Solution (Python):
N = int(input())
L = [int(input()) for i in range(N)]


P = [0] * (N + 1)

for p in L:
    P[p] = P[p-1] + 1


print(N-max(P))

Solution (Python):
n=int(input())
a=[]
for i in range(n):
  x=int(input())
  a.append(x)
d={}
f=0
maxi=0
for i in range(n):
  if((a[i]-1) in d):
    d[a[i]]=d[a[i]-1]+1
  else:
    d[a[i]]=1

for i in d:
  if(i==0):
    maxi=d[i]
  else:
    if(d[i]>maxi):
      maxi=d[i]

print(n-maxi)

Solution (Python):
N = int(raw_input())
P = []
p_hash = {}
for i in range(N):
    num = int(raw_input())
    P.append(num)
    p_hash[num] = i

now_pos = p_hash[1]
count_1 = 1
max_1 = 1
for i in range(1,N):
    pos_new = p_hash[i+1]
    if pos_new > now_pos:
        count_1 += 1
        max_1 = max(max_1,count_1)
        now_pos = pos_new
    else:
        max_1 = max(max_1,count_1)
        count_1 = 1
        now_pos = pos_new

print(N - max_1)

Solution (Python):
n = int(input())
lens = [False for i in range(n + 1)]

for i in range(n):
    p = int(input())
    lens[p] = True
    lens[p - 1] = False

ps = []
for i in range(n + 1):
    if lens[i]:
        ps.append(i)

ps.sort()
x = 0
temp = 0
for i in ps:
    x = max(i - temp, x)
    temp = i
print(n - x)

Solution (Python):
n=int(input())
a=[]
for i in range(n):
     a.append([int(input()),i+1])
a=sorted(a,key=lambda x:x[0])

ans=0
count=0
bef=0
for i,j in a:
    if j>bef:
        count+=1
        ans=max(ans,count)
    else:
        count=1
    bef=j
print(n-ans)

Solution (Python):
N = int(input())

l = list(range(N))

for n in range(N):
    l[n] = int(input())



count_l = []
ind_list = [0] * N

for i, k in enumerate(l):
    ind_list[k-1] = i

count = 1
for i in range(N):
    if i == N - 1:
        count_l.append(count)
    else:
        if ind_list[i] < ind_list[i+1]:
            count += 1
        else:
            count_l.append(count)
            count = 1

print(N - max(count_l))

Solution (Python):
N = int(input())
a = [int(input()) for i in range(N)]
b = [0]*N
for i in range(N):
    b[a[i] - 1] = i
b.append(-1)
count = 1
max = 0
for i in range(N):
    if b[i+1] - b[i] > 0:
        count = count + 1
    else:
        if count > max:
            max = count
        count = 1

print(N - max)

Solution (Python):
N = int(input())

Ps = [(int(input()), i) for i in range(N)]
Ps.sort()

num = 0
ans = 0
for i in range(N - 1):
    if Ps[i][1] < Ps[i + 1][1]:
        num += 1
    else:
        ans = max(ans, num)
        num = 0
    
ans = max(ans, num)
print(N - ans - 1)

Solution (Python):
def main():
    n = int(input())
    p = [int(input()) for _ in range(n)]

    idx = make_index(p)
    c = count_sequence(p, idx)
    ans = n - c
    print(ans)

def make_index(p):
    idx = dict()
    for i, v in enumerate(p):
        idx[v] = i
    return idx

def count_sequence(p, idx):
    cmax = 0
    c = 0
    i = -1

    x = 1
    while True:
        j = idx.get(x, None)
        if j is None:
            cmax = max(cmax, c)
            break
        elif j < i:
            cmax = max(cmax, c)
            c = 1
            i = j
        else:
            c += 1
            i = j
        x += 1

    return cmax

main()

Solution (Python):
import sys,collections,random,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
d = collections.defaultdict(int)
for i in range(n):
    d[I()] = i
d[0] = n
t,maxinc = 0,0
for i in range(1,n+1):
    if d[i-1] < d[i]:
        t += 1
        maxinc = max(maxinc,t)
    else:
        t = 0
print(n-1-maxinc)

Solution (Python):

from itertools import combinations
def inpl(): return map(int, input().split())

N = int(input())
P = [int(input()) for _ in range(N)]
score = [0]*(N+1)

for p in P:
    score[p] = score[p-1] + 1

print(N - max(score))

Solution (Python):

N = int(input())
B= [0] * N

for i in range(0, N):
	bb = int(input())
	B[bb-1] = i

m = 1
mx = 1
for i in range(1, N):
	if B[i] > B[i-1]:
		m = m + 1
		mx = max(mx, m)
	else:
		m = 1

print(N - mx)

Solution (Python):
n = int(input())
p = [0] * (n + 1)
for i in range(n):
    p[int(input())] = i

maxSet = 0

temp = 1
i = 2
while i <= n:
    if p[i - 1] < p[i]:
        temp += 1
        i += 1
    else:
        maxSet = max(maxSet, temp)
        temp = 1
        i += 1
maxSet = max(maxSet, temp)
print(n - maxSet)

Solution (Python):
N = int(input())
union_find = [i for i in range(N)]
def find(n, P):
	if P[n] == n:
		return n
	else:
		x = find(P[n], P)
		P[n] = x
		return x

def append(n, P):
	P[n] = n - 1
	find(n, P)

P = []
for i in range(N):
	p = int(input()) - 1
	P.append(p)

appeared = [False for i in range(N)]
for i in range(N):
	n = P[i]
	appeared[n] = True
	if n != 0 and appeared[n - 1]:
		append(n, union_find)

cont = 0

for i in range(N):
	cont = max(cont, i - find(i, union_find) + 1)
print(N - cont)

Solution (Python):


def main():
	n = int(input())
	ps = {int(input()):i for i in range(n)}
	

	out = 0
	cnt = 1
	tmp = 0
	for i in range(1, n):
		
		if ps[i+1] >= ps[i]:
			cnt += 1
		else:
			out = max(cnt, out)
			cnt = 1
	else:
		if out == 0:
			out = n 
		else:
			out = max(cnt, out)

	print(n - out)

if __name__ == '__main__':
	main()

Solution (Python):
def main():
    N=int(input())
    p=[False]*(N+1)
    c=[False]*(N+1)
    for i in range(N):
        x=int(input())
        c[x]=True
        if c[x-1]:
            p[x-1] = True
    ans=0
    j=0
    for i in range(1,N+1):
        if p[i]:
            j+=1
        else:
            ans=max(ans,j)
            j=0
    ans=max(ans,j)
    print(N-ans-1)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
P = [0]*N
for i in range(N):
	P[i] = int(input())

cnt = [0]*(N+1)
for i in range(N):
	cnt[P[i]] = cnt[P[i]-1] + 1

a = 0
for i in range(N):
	a = max(a, cnt[i+1])
print(N - a)