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 math
N  = int(input())
左端 = [False] * (N + 1)
参照 = [False] * (N + 1)
places = [-1] * ( N + 1)
for ind in range(N):
    temp = int(input())
    places[temp] = ind
for num in range( 1,N + 1):
    if 参照[num] == False:
        左端[num] = True
        l = 1
        while True:
            if num + l <= N and places[num+ l - 1] < places[num + l]:
                参照[num + l] = True
                l += 1
            else:
                break

hoge = 0
for i in range(1 ,N  + 1):
    if 左端[i]:
        cot = 1
        l = i + 1
        while True:
            if l <= N and 参照[l]  :
                cot += 1
                l += 1
            else:
                break
        hoge = max(cot,hoge)
print(N - hoge)

Solution (Python):
import sys
read = sys.stdin.readline


def solve():
    N = int(read())
    P = [0] * N
    for i in range(N):
        P[i] = int(read())
    
    dp = [0] * (N + 1)
    ans = 0
    for i in range(N):
        p = P[i]
        dp[p] = dp[p - 1] + 1
        ans = max(ans, dp[p])
    print(N - ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


def main():
    N = int(input())
    F = [0] * N
    for i in range(N):
        P = int(input()) - 1
        F[P] = i

    res = 0
    tmp = 0
    pre = -1
    for f in F:
        if pre < f:
            tmp += 1
        else:
            res = max(res, tmp)
            tmp = 1
        pre = f
    res = max(res, tmp)
    print(N - res)


if __name__ == "__main__":
    main()

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

Solution (Python):


N=int(input())

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


root=[-1]*N
count=[0]*N
for item in P:
    if item == 0:
        root[item]=item
        count[root[item]]+=1
        continue
    if root[item-1]==-1:
        root[item]=item
        count[root[item]]+=1
    else:
        root[item]=root[item-1]
        count[root[item]]+=1
"""
print(root)
print(count)
print("===========================")
"""
print(N-max(count))

Solution (Python):
N = int(input())
P = [int(input()) for i in range(N)]
ind = [0 for i in range(N)]
for i in range(N):
    ind[P[i]-1] = i
ans = 0
now = 1
for i in range(1,N):
    if ind[i] > ind[i-1]:
        now+=1
    else:
        ans = max(ans,now)
        now = 1
ans = max(ans,now)
print(N-ans)

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

L = [1]*(N+1)
for i in range(N):
    if P[i] < N and L[P[i]+1] == 1:
        L[P[i]+1] = L[P[i]]+1
    if L[P[i]] == 1:
        L[P[i]] = 0

ans = N-max(L)
print(ans)

Solution (Python):
def main():
    N,*P=map(int, open(0).read().split())
    X=[0]*(N+1)
    for p in P:
        X[p]=max(X[p],X[p-1]+1)
    print(N-max(X))

if __name__ == "__main__":
    main()

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

ma = 1
s = 0
for i in range(1, N):
    if X[i] < X[i-1]: s = i
    ma = max(ma, i - s + 1)

print(N - ma)

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

ma = 1
s = 0
for i in range(1, N):
    if X[i] < X[i-1]: s = i
    ma = max(ma, i - s + 1)

print(N - ma)

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

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

ans,cnt = 0,0
work = -1
for i in range(N):
  if work < A[i]:
    cnt += 1
    ans = max(ans, cnt)
  else:
    cnt = 1
  work = A[i]

print(N-ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inn())
b = [0]*(n+1)
for i in range(n):
    b[a[i]] = b[a[i]-1]+1
print(n-max(b))

Solution (Python):
n = int(input())
p = []
for _ in range(n):
    p.append(int(input()))
from collections import defaultdict
d = defaultdict(int)
for num in p:
    d[num] = d[num-1]+1
print(n-max(d.values()))

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
permu_index = {}
for i in range(N):
    permu_index[P[i]] = i
ans = []
for i in range(1, N+1):
    ans.append(permu_index[i])
max_len = 0
tmp = 1
now = ans[0]
for a in ans[1:]:
    if a > now:
        tmp += 1
        now = a
    else:
        max_len = max(max_len, tmp)
        now = a
        tmp = 1
max_len = max(max_len, tmp)
print(N-max_len)

Solution (Python):
import sys
input = sys.stdin.readline   


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

q = [0] * n
for i in range(n):
    q[p[i]-1] = i
mxk = 1
k = 1
for i in range(n-1):
    if q[i] < q[i+1]:
        k += 1
        if k > mxk:
            mxk = k
    else:
        k = 1
print(n-mxk)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

q = [0] * n
for i in range(n):
    q[p[i]-1] = i
mxk = 1
k = 1
for i in range(n-1):
    if q[i] < q[i+1]:
        k += 1
        if k > mxk:
            mxk = k
    else:
        k = 1
print(n-mxk)

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
mxk = 1
k = 1
for i in range(n-1):
    if q[i] < q[i+1]:
        k += 1
        if k > mxk:
            mxk = k
    else:
        k = 1
print(n-mxk)

Solution (Python):
from operator import itemgetter
n=int(input())
p=[int(input()) for i in range(n)]
d=dict()
for i in range(n):
  if p[i]-1 not in d:
    d[p[i]]=1
  else:
    d[p[i]]=d[p[i]-1]+1
d=list(d.items())
d.sort(reverse=True,key=itemgetter(1))
print(n-d[0][1])

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
p=[int(input()) for i in range(n)]
lst=[0]*(n+2)
for i in range(n):
    lst[p[-1-i]]=lst[p[-1-i]+1]+1

print(n-max(lst))

Solution (Python):
n=int(input())
p=[int(input()) for _ in range(n)]
dp=[0]*(n+10)
for i in p:
  dp[i]=dp[i-1]+1
print(n-max(dp))

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

def solve():
    O=[-1]*(N+1)
    for i,p in enumerate(P): O[p]=i

    n=0
    nn=0
    for i in range(1,N+1):
        if O[i-1]<O[i]: n+=1
        else: n=1
        nn=max(nn,n)

    return N-nn

print(solve())
'''
from itertools import permutations
for p in permutations(range(N)):
    P=list(map(lambda x:x+1,p))
    print(P,solve())
'''

Solution (Python):

import re
import math
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline

mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="number"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True

fac=fac_list(10**5+100,mod)
def C(n,r):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod

 

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

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

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

q=[-1]*N
for i in range(N):
    k = int(input())
    
    q[k-1]=i


max_con=1
count=1
for i in range(N-1):
    if q[i]<q[i+1]:
        count+=1
        max_con=max(max_con,count)
    else:
        count=1

print(N-max_con)

Solution (Python):

def main():
    N = int(input())
    a=[]
    for i in range(N):
        a.append(int(input()))

    b = [0 for _ in range(N+2)]
    cnt = 1
    ans = 0
    flag = 1
    i = 0
    for i in reversed(range(N)):
        if b[a[i]+1] > 0:
            b[a[i]] = b[a[i]+1] + 1
        else:
            b[a[i]] = 1
        
    return N-max(b)
print(main())

Solution (Python):

import sys


def solve(N: int, P: "List[int]"):
    sorted_lis = sorted([(n, i) for i, n in enumerate(P)])
    max_con = 1
    con_cnt = 0
    pre_idx = N
    for _, i in sorted_lis:
        if i > pre_idx:
            con_cnt += 1
        else:
            max_con = max(max_con, con_cnt)
            con_cnt = 1
        pre_idx = i
    max_con = max(max_con, con_cnt)
    print(N - max_con)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = [int(next(tokens)) for _ in range(N)]  
    solve(N, P)

if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
data=[int(input()) for i in range(N)]
count=0
dic={}
for i in data:

    if i-1 in dic:
        num=dic.pop(i-1)
        dic.update({i:num+1})
    else:
        dic.update({i:1})
print(N-max([dic[i] for i in dic]))

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline









N, = map(int, input().split())
L = [int(input()) for _ in range(N)]

f = False
t = defaultdict(int)
for i in range(N):
    if t[L[i] - 1] != 0:
        t[L[i]] = t[L[i] - 1] + 1
        t[L[i] - 1] = 0
    else:
        t[L[i]] = 1

print(N - max(t.values()))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

B = [0] * N
for i, a in enumerate(A):
    B[a-1] = i

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

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
hist = [0 for _ in range(N+1)]
A = {i:0 for i in range(1,N+1)}
for i in range(N):
    a = P[i]
    if hist[a-1]==0:
        A[a] = a
    else:
        A[a] = A[a-1]
    hist[a] = 1
cmax = 0
for i in range(1,N+1):
    cmax = max(cmax,i-A[i]+1)
print(N-cmax)

Solution (Python):
n = int(input())
p = [int(input()) for i in range(n)]
q = [0] * n
now = 1
for k,v in enumerate(p):
  q[v-1] = k
now = -1
ans = 1
mini_ans = 0
for i in q:
  if i > now:
    mini_ans += 1
  else:
    ans = max(ans,mini_ans)
    mini_ans = 1
  now = i
ans = max(ans,mini_ans)
ans = n-ans
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
ls = [0 for i in range(n)]
for i in range(n):
  x = a[i]
  ls[x-1] = i+1
cnt = 1
ans = 0
ls.append(0)
for i in range(1,n+1):
  if ls[i]>ls[i-1]:
    cnt += 1
  else:
    ans = max(ans,cnt)
    cnt = 1
print(n-ans)

Solution (Python):
n = int(input())
P = [int(input()) for _ in range(n)]
Q = [0]*(n+1)
for i, j in enumerate(P):
  Q[j-1] = i+1
count = 0
m = 0
for i in range(n):
  count += 1
  if Q[i] > Q[i+1]:
    m = max(m, count)
    count = 0
print(n-m)

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

S = [0]*(N+1)

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

print(N-max(S))

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

S = [0]*(N+1)

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

print(N-max(S))

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

S = [0 for _ in range(N+1)]

for i in range(N):
    if S[P[i]-1]!=0:
        S[P[i]] = S[P[i]-1]+1
    else:
        S[P[i]] = 1
    
print(N-max(S))

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

LIS = [0] * (N + 1)

for i in range(N):
  LIS[P[i]] = LIS[P[i] - 1] + 1
print(N - max(LIS))

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

a = [0 for i in range(n)]

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

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

Solution (Python):
class UnionFind:
    
    def __init__(self, n):
        
        self.par = [-1] * n
        
        self.rank = [0] * n

    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x != y:
            
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            
            self.par[x] += self.par[y]
            self.par[y] = x

    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    
    def size(self, x):
        return -self.par[self.find(x)]


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

already = [0 for i in range(n+1)]
group = UnionFind(n+1)
for x in p:
    already[x]=1
    if already[x-1]==1:
        group.unite(x,x-1)

ans = n
for x in p:
    ans=min(ans,n-group.size(x))

print(ans)

Solution (Python):
N = int(input())
P = []
indexls = [0]*N
for i in range(N):
    tmp = int(input())
    P.append(tmp)
    indexls[tmp-1] = i
maxlen = 1
tmplen = 1
for i in range(1,N):
    if indexls[i] > indexls[i-1]:
        tmplen += 1
        maxlen = max(maxlen,tmplen)
    else:
        tmplen = 1
print(N-maxlen)

Solution (Python):

N = int(input())

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

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



max_cnt = 0
curr = 0
for i in range(N):
    if i == 0:
        max_cnt = 1
        curr = 1
    else:
        
        if idxs[i] > idxs[i-1]:
            curr += 1
            max_cnt = max(max_cnt, curr)
        else:
            curr = 1
    

print(N - max_cnt)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    n = inp()
    p = inplm(n)
    q = [0 for _ in range(n)]
    for i in range(n):
        q[p[i]-1] = i
    x = 1
    y = 1
    for i in range(n-1):
        if q[i]<q[i+1]:
            x += 1
        else:
            y = max(x,y)
            x = 1
    print(n-max(x,y))

if __name__ == "__main__":
    main()

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

cnt = 0
ans = 0
for x, y in zip(order[:-1], order[1:]):
    if x > y:
        ans = max(cnt, ans)
        cnt = 0
    else:
        cnt += 1
ans = max(cnt, ans)

answer = n - ans - 1
print(answer)

Solution (Python):
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

N = ri()
P = [ri() for _ in range(N)]

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

print(N-max(dp))

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
index = [-1] * N
for i, p in enumerate(P):
    index[p-1] = i
res = 1
tmp = 1
for i in range(N-1):
    if index[i] < index[i+1]:
        tmp += 1
        res = max(res, tmp)
    else:
        tmp = 1
ans = N-res
print(ans)

Solution (Python):
def examB():
    N = I(); P = [I() for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        d[P[i]] = d[P[i]-1]+1
    ans = N-max(d.values())
    d = defaultdict(int)
    for i in range(N-1,-1,-1):
        d[P[i]] = d[P[i]+1]+1
    ans = min(ans,N-max(d.values()))
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

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

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

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

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

A = {}
for i, p in enumerate(P):
    A[p] = i

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

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

pos = [0] * N
for i in range(N) :
    pos[P[i] - 1] = i
    
ret = 0
c = 1
for i in range(1, N) :
    if pos[i] > pos[i - 1] :
        c += 1
    else :
        ret = max(ret, c)
        c = 1
ret = max(ret, c)
        
print(N - ret)

Solution (Python):
n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
d={}
for i in range(n):
  d[l[i]]=i+1
ans=1
ans1=1
index=1
while index<n:
  index+=1
  if d[index]>d[index-1]:
    ans1+=1
  else:
    if ans<ans1:
      ans=ans1
    ans1=1
if ans<ans1:
  ans=ans1
print(n-ans)

Solution (Python):
import sys
from operator import itemgetter
read = sys.stdin.read

N, *P = map(int, read().split())
p = sorted(enumerate(P), key=itemgetter(1))

length = []
cnt = 1
for i in range(N - 1):
    if p[i + 1][0] < p[i][0]:
        length.append(cnt)
        cnt = 1
    else:
        cnt += 1

length.append(cnt)

print(N - max(length))

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]
B = [[A[i], i+1] for i in range(N)]
B.sort(key=lambda x: x[0])
dp = [1]*N

for i in range(1, N):
    if B[i-1][1] < B[i][1]:
        dp[i] = dp[i-1]+1

ans = N - max(dp)

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
p=[int(input()) for _ in range(n)]
q=[0]*(n+1)
for i in range(n):
    q[p[i]]=i+1

q=q[1:]
m=0
k=1
for i in range(1,n):
    if q[i]>q[i-1]:
        k+=1
    else:
        m=max(m,k)
        k=1
m=max(m,k)
print(n-m)

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


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

Solution (Python):
n=int(input())
p=[int(input()) for i in range(n)]
dp=[0]*n
ans=0
for i in range(n):
  if p[i]!=1:
    dp[p[i]-1]=dp[p[i]-2]+1
  else:
    dp[0]=1
print(n-max(dp))

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
LIS = [0] * (N + 1)
P = [0]*N
for i in range(N):
    P[i] = int(stdin.readline().rstrip())
for p in P:
    LIS[p] = LIS[p-1] + 1 
print(N - max(LIS))

Solution (Python):
def main():
    import bisect
    n=int(input())
    a=[int(input()) for _ in [0]*n]
    b=[[a[i],i] for i in range(n)]
    b.sort()
    cnt=1
    ans=1
    for i in range(1,n):
        if b[i-1][1]<b[i][1]:
            cnt+=1
            ans=max(cnt,ans)
        else:
            cnt=1
    print(n-ans)
main()

Solution (Python):

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

check = [0] * (n+1)
sor = [0] * (n+1)

for i in range(n):
    if check[p[i]-1] == 1:
        sor[p[i]] = 1
    check[p[i]] = 1



count = 0
tmp = 0
for i in range(n+1):
    if sor[i] == 1:
        tmp += 1
    else:
        count = max(count, tmp)
        tmp = 0
count = max(count, tmp)

print(n - count - 1)

Solution (Python):
n = int(input())
P = [int(input())-1 for i in range(n)]

A = [0] * n
for i in range(n):
    A[P[i]] = i

ans = 1
ans1 = 1
for i in range(1, n):
    if A[i] > A[i-1]:
        ans1 += 1
    else:
        ans = max(ans1, ans)
        ans1 = 1
ans = max(ans1, ans)

print(n - ans)

Solution (Python):
n=int(input())
d={}
for i in range(n):
    p=int(input())
    d[p]=i+1
ans=s=1
while s<n:
    f=d[s]
    cnt=0
    for i in range(s,n+1):
        if d[i]>=f:
            f=d[i]
            s=i
            cnt+=1
        else:
            s=i
            break
    ans=max(ans,cnt)
print(n-ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

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


def main():
	N = int(input())
	L = []
	for i in range(N):
		P = int(input())
		L.append([P, i])
	L = sorted(L)
	ans_pre = 1
	val = 1
	for i in range(N - 1):
		if L[i + 1][1] > L[i][1]:
			val += 1
		else:
			ans_pre = max(ans_pre, val)
			val = 1
	ans_pre = max(ans_pre, val)

	ans = N - ans_pre
	print(N - ans_pre)

if __name__ == '__main__':
	main()

Solution (Python):

n = int(input())
p = [int(input()) for i in range(n)]
f = [0]*(n+1)
m = [n-1]*(n+1)
for i in p:
    if f[i-1]:
        m[i] = m[i-1]-1
    f[i] = 1
print(min(m))

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

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

count = 1
i = 1
while i < N: 
    tmp = i
    
    tmp_count = 1
    while tmp < N and lst[tmp] < lst[tmp + 1]:
        tmp_count += 1
        tmp += 1
    count = max(count, tmp_count)
    i = tmp + 1

print (N - count)

Solution (Python):



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

    
    
    
    

    
    

    
    
    
    
    p = [0 for _ in range(n)]

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

    len_max = 1
    count = 1

    for i in range(1, n):
        if p[i] > p[i - 1]:
            count += 1
        else:
            count = 1

        
        
        len_max = max(len_max, count)

    print(n - len_max)


if __name__ == '__main__':
    main()

Solution (Python):



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

    
    
    
    

    
    

    
    
    
    
    p = [0 for _ in range(n)]

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

    len_max = 1
    count = 1

    for i in range(1, n):
        if p[i] > p[i - 1]:
            count += 1
        else:
            count = 1

        len_max = max(len_max, count)

    print(n - len_max)


if __name__ == '__main__':
    main()

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

lis = [0] * (N+1)

for i in range(N):

    P = int(input())

    lis[P] = lis[P-1] + 1

print (N - max(lis))

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N = I()
P = Line(N,1)

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

max_ascend = 0
temp = 1
for i in range(2,N+1):
    if place[i]>place[i-1]:
        temp += 1
    else:
        if max_ascend<temp:
            max_ascend = temp
        temp = 1

if max_ascend<temp:
    max_ascend = temp

print(N-max_ascend)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for i in range(N)]

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

    print(N - max(dp))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(input()) for i in range(N)]

    dp = [0] * N
    
    for i in range(N):
        if A[i] > 1:
            dp[A[i]-1] = dp[A[i]-2] + 1
        elif A[i] == 1:
            dp[A[i]-1] = 1
    print(N - max(dp))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
p = [0]*n
p2 = []
for i in range(n):
    m = int(input())
    p[m-1] = i
    p2.append(m)

succ = [1] * n

for i in range(1,n):
    if p[i-1] < p[i]:
       succ[i] = succ[i-1] + 1

"""
print(p2)
print(p)
print(succ)
"""

print(n-max(succ))

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

cnt=0
count=1
for i in range(n):
    if uselist[i]<uselist[i+1]:
        count+=1
    else:
        cnt=max(count,cnt)
        count=1
print(n-cnt)

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


"""
t, t+1, t+2,... のように、差が１かつ単調増加で並んでいる部分列の最大長さが動かさないでいい数。
なので、２が１より右にあるか、３が２より右にあるか、...を、見ていき、t+1がtの右にない時点である部分列は終わり。
その最大長さを要素数から引いたものが答え

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

cnt = 1
max_len = 1
for i, j in zip(idxs[1:], idxs[2:]):
    if i < j:
        cnt += 1
        max_len = max(cnt, max_len)
    else:
        cnt = 1

print(N - max_len)

Solution (Python):
n=int(input())
l=[]
ll=[0]*(n+1)
s=set()
for i in range(n):
    p=int(input())
    l.append(p)
    ll[p]=i
tmp=0
ans=0
b=-1
for i in range(1,n+1):
    if b<ll[i]:
        tmp+=1
    else:
        tmp=1
    b=ll[i]
    ans=max(ans,tmp)
print(n-ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 998244353


n = I()
P = IR(n)
LIS = [0] * (n + 1)
for i in range(n):
    LIS[P[i]] = LIS[P[i] - 1] + 1



print(n - max(LIS))

Solution (Python):
d={}
for x in map(int,open(0)):d[x]=d.get(x-1,0)+1
print(len(d)-max(d.values()))

Solution (Python):
N,*P=map(int,open(0))
ids=[0]*N
for i in range(N):
	ids[P[i]-1]=i
tmp=inc=1
for i in range(N-1):
	if ids[i]<ids[i+1]:
		tmp+=1
		inc=max(tmp,inc)
	else:
		tmp=1
print(N-inc)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
memo = [0 for i in range(n)]
for i in range(n):
  memo[int(input())-1] = i
cand = 0
tmp = 0
for n1, n2 in zip(memo[:], memo[1:]):
  if n2 > n1:
    tmp += 1
    if tmp > cand:
      cand = tmp
  else:
    tmp = 0
print(n - cand - 1)

Solution (Python):
import sys
input=sys.stdin.readline

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

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

    print(N-max(Q))

if __name__ == '__main__':
    main()

Solution (Python):

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

count = [0 for i in range(N)]
now = [-1 for i in range(N+1)]
for i in range(N):
    if P[i] == 1:
        now[P[i]-1] = P[i]
        count[P[i]-1]+=1
    elif now[P[i]-2] == -1:
        now[P[i]-1] = P[i]
        count[P[i]-1]+=1
    else:
        now[P[i]-1] = P[i]
        count[P[i]-1] = count[P[i]-2]+1
        

MAX = max(count)
ans = N-MAX
print(ans)

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
res = 0
temp = 0
for i in range(2, N + 1):
  if q[i - 1]  < q[i]:
    temp += 1
  else:
    res = max(res, temp)
    temp = 0
res = max(res, temp)
print(N - res - 1)

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


S = [0 for _ in range(N+1)]
for i in range(N):
  S[P[i]] = S[P[i]-1] + 1
print(N-max(S))