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):
n = int(input())
p = [int(input()) for _ in range(n)]



p_with_index = list(sorted(enumerate(p), key=lambda x : x[1]))
max_inc_span = 1
span = 1
for i in range(1, n):
    if p_with_index[i-1] < p_with_index[i]:
        span += 1
        max_inc_span = max(max_inc_span, span)
    else:
        span = 1

print(n - max_inc_span)

Solution (Python):

import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    
    n = input_int()
    dp = [0] * (n + 1)
    
    

    for _ in range(n):
        a = input_int()
        dp[a] = dp[a - 1] + 1

    ans = n - max(dp)
    print(ans)

    return


if __name__ == "__main__":
    main()

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

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

for i in range(n):
  a=int(input())
  ans[a-1]+=(i+1)
  
ch=1

ans1=[1]
  
for x in range(n-1):
  if ans[x]<ans[x+1]:
    ch+=1
    
  else:
    ans1.append(ch)
    ch=1
  
  if x==n-2:
    ans1.append(ch)
  
    
print(n-max(ans1))

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+1
cnt=1
curcnt=0
for i in range(1,n+1):
    if q[i]>q[i-1]:
        curcnt+=1
        cnt=max(cnt,curcnt)
    else:
        curcnt=1

print(n-cnt)

Solution (Python):
def main():
    n = int(input())
    p = []
    for _ in range(n):
        p.append(int(input()))
    q = [0 for i in range(n)]
    for i in range(n):
        q[p[i]-1] = i
    m,cnt = 1,1
    for i in range(1,n):
        if q[i]>q[i-1]:
            cnt += 1
            if cnt > m:
                m = cnt
        else:
            cnt = 1
    print(n-m)

if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
p=[]
for i in range(n):
  p.append((int(input()),i))
p.sort()
l=-1
s=0
mx=0
for i in range(n):
  if p[i][1]>l:
    s+=1
    mx=max(mx,s)
  else:
    s=1
  l=p[i][1]
print(n-mx)

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

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

for p in P:
    dp[p] = dp[p-1]+1
    
print(N-max(dp))

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=[int(input())-1 for _ in range(n)]
length=[-1]*n
for i in range(n):
    if i==0 or p[i]==0:
        length[p[i]]=0
    else:
        if (pre:=length[p[i]-1])==-1:
            length[p[i]]=0
        else:
            length[p[i]]=length[p[i]-1]+1
print(n-max(length)-1)

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

Solution (Python):
N, *P = map(int, open(0).read().split())
pairs = sorted((P[i], i) for i in range(N))

sub = 1
right = 0
for left in range(N):
    while right < N - 1 and pairs[right + 1][1] > pairs[right][1]:
        right += 1

    sub = max(sub, right - left + 1)

    if left == right:
        right += 1
print(N - sub)

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

arr=[(P[i],i) for i in range(N)]
arr.sort()

i=0
L=0

while(i<N):
    j=i
    while(j<N-1 and arr[j+1][1]>arr[j][1]):
        j+=1
    L=max(L,j-i+1)
    i=j+1
print(N-L)

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

Solution (Python):
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())

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

m = 0
streak = 1
for a,b in zip(T,T[1:]):
    if a < b:
        streak += 1
    else:
        m = max2(m, streak)
        streak = 1
m = max2(m, streak)

print(N-m)

Solution (Python):
from collections import Counter

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

lst = [False] * (n + 1)
for num in p:
    bfo = lst[num - 1]
    if bfo:
        lst[num] = bfo
    else:
        lst[num] = num
cnt = Counter(lst).values()
print(n - max(cnt))

Solution (Python):
from collections import Counter

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

lst = [-1] * (n + 1)
for num in p:
    bfo = lst[num - 1]
    if bfo == -1:
        lst[num] = num
    elif bfo > 0:
        lst[num] = bfo
cnt = Counter(lst).values()
print(n - max(cnt))

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

lst = [0] * (n + 1)
for num in p:
    bfo = lst[num - 1]
    if bfo == 0:
        lst[num] = -1
    elif bfo < 0:
        lst[num] = num - 1
        lst[num - 1] -= 1
    elif bfo > 0:
        lst[num] = bfo
        lst[bfo] -= 1
print(n + min(lst))

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

Solution (Python):
d = {}
N = int(input())
p = [int(input()) for i in range(N)]

for i in range(N):
    if((p[i]-1) in d):
        d[p[i]] = d[p[i]-1] + 1
    else:
        d[p[i]] = 1

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

Solution (Python):
n = int(input())
l = [0]*(n+1)
for i in range(n):
    x = int(input())
    l[x] = l[x-1]+1
print(n-max(l))

Solution (Python):
n = int(input())
P = [int(input())-1 for _ in range(n)]
A = [0]*n
for i, p in enumerate(P):
    A[p] = i



m = 0
temp = 0
for i in range(1, n):
    if A[i-1] < A[i]:
        temp += 1
    else:
        m = max(m, temp)
        temp = 0
else:
    m = max(temp, m)
print(n-m-1)

Solution (Python):
n = int(input())
P = [int(input())-1 for _ in range(n)]
A = [0]*n
for i, p in enumerate(P):
    A[p] = i



m = 0
temp = 0
for i in range(1, n):
    if A[i-1] < A[i]:
        temp += 1
    else:
        m = max(m, temp)
        temp = 0
else:
    m = max(temp, m)
print(n-m-1)

Solution (Python):
import sys
import math
import copy
import random
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]


class BIT():
    
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def update(self, idx, x):
        
        while idx <= self.n:
            
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)


def solve():
    n = getN()
    li = []
    for i in range(n):
        li.append(getN())

    slis = [0 for i in range(n+10)]

    for num in li:
        slis[num] = slis[num-1] + 1

    print(n - max(slis))


def main():
    n = getN()
    for _ in range(n):
        s = "".join([random.choice(["F", "T"]) for i in range(20)])
        print(s)
        solve(s, 1, 0)

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    P = [I() for _ in range(N)]

    
    
    enum_P = [(i, e) for e, i in enumerate(P)]
    enum_P.sort()
    

    cis = []
    tmp = []
    for i in range(N):
        tmp.append(enum_P[i][1])
        if i < N - 1 and enum_P[i][1] > enum_P[i+1][1]:
            cis.append(tmp)
            tmp = []
    cis.append(tmp)

    ans = N - max([len(i) for i in cis])
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):

N = int(input())
a = []
for _ in range(N):
    x = int(input())
    a.append((_, x))
a.sort(key=lambda x: x[1])
a.append((-10000000000000000, 10**20))
cnt, now, maxi = 0, -1, 0
for p, v in a:
    if now < p:
        cnt += 1
        now = p
    elif now > p:
        maxi = max(maxi, cnt)
        cnt = 1
        now = p
print(N-maxi)

Solution (Python):
n=int(input())
p=[int(input()) for _ in range(n)]
s=set()
for i in p:
  if i-1 in s:s-={i-1}
  s|={i}
s=[0]+sorted(list(s))
ans=n
for i in range(len(s)-1):
  ans=min(ans,n-s[i+1]+s[i])
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



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

dp = [0]*(N+1)

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

print(N-max(dp))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



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

cnt = [0]*(N+1)

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

print(N-max(cnt))

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


if __name__ == '__main__':
    main()

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

cnt = [0] * n

for i in range(n):
    if p[i] == 0:
        cnt[0] = 1
    else:
        cnt[p[i]] = cnt[p[i] - 1] + 1

max_p = max(cnt)

print(n - max_p)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    
    n=I()
    list_=LI2()
    dict_=defaultdict(lambda:x)
    for i in range(n):
        dict_[list_[i]]=i
    mx=0
    length=1
    ind=1
    while ind<n:
        if dict_[ind]<dict_[ind+1]:
            length+=1
            ind+=1
        else:
            mx=max(length,mx)
            length=1
            ind+=1
    mx=max(length,mx)
    print(n-mx)
    
    



if __name__=="__main__":
    main()

Solution (Python):
def agc024_b():
    n = int(input())
    P = [int(input())-1 for _ in range(n)]  
    if n == 1: return print(0)

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

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

    ans = n - (cmax + 1)
    print(ans)

if __name__ == '__main__':
    agc024_b()

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

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

for i in range(n):
    posi[a[i]]=i

cnt=0
ans=0
p=0

for i in range(n):
    if p<=posi[i]:
        cnt+=1
        p=posi[i]
        ans=max(ans,cnt)
    else:
        p=posi[i]
        cnt=1
    


print(n-ans)

Solution (Python):


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


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


def solve():
    N = read_int()
    Q = [0]*N
    for i in range(N):
        Q[read_int()-1] = i
    max_k = 1
    k = 1
    for i in range(1, N):
        if Q[i] > Q[i-1]:
            k += 1
            max_k = max(max_k, k)
        else:
            k = 1
    return N-max_k


if __name__ == '__main__':
    print(solve())

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    l = [0] * (N + 1)
    for n in range(N):
        p = int(input())
        l[p] = l[p-1] + 1
    print(N - max(l))

if __name__ == '__main__':
    main()

Solution (Python):
import sys,math,collections,itertools
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

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

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    P = [None] * N
    for i in range(N):
        P[i] = int(input())

    dp = [0] * (N + 1)
    for p in P:
        dp[p] = dp[p - 1] + 1
    
    ans = N - max(dp)
    print(ans)


if __name__ == "__main__":
    main()

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


def read():
    N = int(input().strip())
    P = []
    for i in range(N):
        p = int(input().strip())
        P.append(p)
    return N, P


def solve(N, P):
    Q = [0 for i in range(N)]
    for i in range(N):
        Q[P[i]-1] = i
    max_count = 0
    count = 0
    prev = -1
    for i in range(N):
        q = Q[i]
        if prev < q:
            count += 1
            prev = q
        else:
            max_count = max(max_count, count)
            count = 1
            prev = q
    max_count = max(max_count, count)
    return N - max_count


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

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


def read():
    N = int(input().strip())
    P = []
    for i in range(N):
        p = int(input().strip())
        P.append(p)
    return N, P


def solve(N, P):
    h = []
    for i in range(N):
        heapq.heappush(h, (P[i], i+1))
    max_count = 0
    count = 0
    prev = -1
    for _ in range(N):
        p, i = heapq.heappop(h)
        if prev < i:
            count += 1
            prev = i
        else:
            max_count = max(max_count, count)
            count = 1
            prev = i
    max_count = max(max_count, count)
    return N - max_count


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import sys
import math
import collections
import bisect
import copy
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n = ni()
    p = [ni() - 1 for _ in range(n)]

    table = [0] * n

    maxnum = 0
    for i in range(n):
        idx = p[i]
        if idx == 0:
            table[idx] = 1
        else:
            table[idx] = table[idx - 1] + 1
        maxnum = max(maxnum, table[idx])

    print(n - maxnum)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    P = list(int(input()) for _ in range(n))
    cnt = [0] * (n + 1)
    for p in P:
        cnt[p] = cnt[p - 1] + 1

    res = n - max(cnt)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
lst = [0]*(n+1)
for i in range(n):
    lst[int(input())] = i
s = 0
t = 1
for i in range(1,n):
    if lst[i] < lst[i+1]:
        t += 1
    else:
        s = max(t,s)
        t = 1
s = max(t,s)
print(n-s)

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

d = {}
for i in P:
    if i-1 in d.keys():
        d[i] = d[i-1] + 1
    else:
        d[i] = 1

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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())

N = I()
P = [0] + [I() for _ in range(N)]

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



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

print(N-a)

Solution (Python):
def main():
    N = int(input())
    P = [int(input()) - 1 for _ in range(N)]
    indices = [0] * N
    for i, p in enumerate(P):
        indices[p] = i
    max_cnt = 0  
    cur_index, cur_cnt = -1, 0
    for p in range(N):
        index = indices[p]
        if index > cur_index:
            cur_cnt += 1
        else:
            max_cnt = max(max_cnt, cur_cnt)
            cur_cnt = 1
        cur_index = index
    max_cnt = max(max_cnt, cur_cnt)
    print(N - max_cnt)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    N=int(input())
    P=[int(input()) for i in range(N)]
    alr=set()
    iorn=[False]*(N+1)
    for i in range(N):
        if P[i]-1 in alr:
            iorn[P[i]]=True
        alr.add(P[i])
    maxlen=0
    lenn=0
    for i in range(1,N+1):
        if iorn[i]:
            lenn+=1
        else:
            lenn=1
        maxlen=max(maxlen,lenn)
    print(N-maxlen) 
    
    
if __name__=="__main__":
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    idx = {}

    for i, x in enumerate(a):
        idx[x] = i

    mx = 1
    cnt = 1
    for x in range(1, n):
        if idx[x] < idx[x + 1]:
            cnt += 1
            mx = max(mx, cnt)
        else:
            cnt = 1

    print(n - mx)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

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

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

print(N-ans)

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

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


if __name__ == '__main__':
    main()

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

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

    ans = 1
    pre = Q[1]
    cur = 1
    for q in Q[2:]:
        if pre < q:
            cur += 1
        else:
            ans = max(ans, cur)
            cur = 1
        pre = q
    ans = max(ans, cur)
    print(N - ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [0 for _ in range(N+1)]
for _ in range(N):
    a = int(input())
    if A[a-1]==0:
        A[a] = 1
    else:
        A[a] = A[a-1]+1
n = max(A)
print(N-n)

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

D = {p:i for i,p in enumerate(P)}
pv = N
l = seq = 0
for n in range(1,N+1):
    nx = D[n]
    if pv < nx:
        seq += 1
    else:
        l = max(l,seq)
        seq = 1
    pv = nx
l = max(l, seq)

print(N - l)

Solution (Python):
N = int(input())
lis = [0] * N
for i in range(N):
    P = int(input())
    P -= 1
    lis[P] = i
ans = 1
cnt = 1
for i in range(1,N):
    if lis[i] < lis[i-1]:
        cnt = 0
    cnt += 1
    ans = max(ans,cnt)
print(N-ans)

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

dict_i = {}

for i, a in enumerate(la):
    dict_i[a] = i


m = 0
s = 0
j = -1
for a in range(1, n + 1):
    i = dict_i[a]
    if i > j:
        s += 1
        m = max(m, s)
    else:
        s = 1
    j = i

answer = n - m
print(answer)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()
P = getArray(N)

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

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

Solution (Python):
n,*p=map(int,open(0))
q=[0]*-~n
for p in p:q[p]=q[p-1]+1
print(n-max(q))

Solution (Python):
n, *p = map(int, open(0))
q = [0] * -~n
for p in p:
  q[p] = q[p - 1] + 1
print(n - max(q))

Solution (Python):
n = int(input())
l = [int(input()) for _ in range(n)]
cou = [0 for i in range(n+1)]
for i in l:
  cou[i] = cou[i-1]+ 1
print(n-max(cou))

Solution (Python):
n = int(input())
Ps = [int(input())for _ in range(n)]
p_to_i = {p: i for i, p in enumerate(Ps)}

cnt = x = 1
for p in range(1, n):
    if p_to_i[p] < p_to_i[p+1]:
        x += 1
        if cnt < x:
            cnt = x
    else:
        x = 1
print(n-cnt)

Solution (Python):
n = int(input())
cnt = 0
queue = []
last = {}
for _ in range(n):
    p = int(input())
    if p-1 not in last.keys():
        last[p] = len(queue)
        queue.append([p])
        if cnt < 1:
            cnt = 1
    else:
        queue[last[p-1]].append(p)
        last[p] = last[p-1]
        if cnt < len(queue[last[p-1]]):
            cnt = len(queue[last[p-1]])

print(n-cnt)

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

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

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

print(n-ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    P = list(int(input()) for _ in range(n))
    cnt = [0] * (n + 1)
    for p in P:
        cnt[p] = cnt[p - 1] + 1

    res = n - max(cnt)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    P = list(in_all())
    Q = [0] * (N + 1)

    if N == 1:
        print(0)
        exit()

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

    dc = []
    for i in range(1, N):
        if Q[i] < Q[i + 1]:
            dc.append(1)
        else:
            dc.append(0)

    gr = itertools.groupby(dc)

    cnt = 1
    for k, v in gr:
        v = sum(1 for _ in v)
        if k == 1:
            cnt = max(cnt, v + 1)

    print(N - cnt)


if __name__ == '__main__':
    main()

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=int(input())
p=[int(input()) for _ in range(n)]
res=[0]*n
for i in range(n):
    res[p[i]-1]=i

k=1
x=0
if n==1:
  print(0)
  exit()
for i in range(1,n):
    if res[i-1]<res[i]:
        k+=1
    else:
        x=max(x,k)
        k=1
x=max(x,k)
print(n-x)

Solution (Python):



def main():
    N = int(input())
    P = list(int(input()) for _ in range(N))
    dp = [0]*(N+1)   

    ret = 0;
    for p in P:
        dp[p] = dp[p - 1] + 1
        ret = max(ret, dp[p])

    print(N - ret)

if __name__ == '__main__':
    main()

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

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

print(n - max(q))

Solution (Python):
"""
連続する数は動かさず、それ以外を左右に分配していく
⇨並べ替えた後、昇順に連続しているかは、インデックスが昇順になっているかを見る
"""
import sys
input = sys.stdin.readline

n = int(input())
ps = {int(input()):i for i in range(n)}
cnt = 1
prev = 10**10
ans = 0

ps[n+1] = -1
for i in range(1,n+2):
    ind = ps[i]
    if prev < ind:
        cnt += 1
    else:
        ans = max(ans, cnt)
        cnt = 1
    prev = ind
print(n-ans)