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 bisect
n = int(input())
p = [int(input()) for _ in range(n)]
idx = dict()
for i in range(n):
    idx[p[i]] = i
c = 0
cnt = 1
for i in range(1, n):
    if idx[i + 1] > idx[i]:
        cnt += 1
    else:
        c = max(c, cnt)
        cnt = 1
c = max(c, cnt)
print(n - c)

Solution (Python):
N = int(input())
ls = [0]*(N+1)
for i in range(N):
  p = int(input())
  ls[p] = i
ID = -1
count = 0
ans = 0
for a in range(1,N):
  if ls[a+1]>ls[a]:
    count += 1
  else:
    if count>ans:
      ans = count
    count = 0
if count>ans:
  ans = count
print(N-ans-1)

Solution (Python):
n=int(input())
p=[int(input()) for i in range(n)]
l=[-1 for i in range(n)]
for i in range(n):
  l[p[i]-1]=i
ans=[]
ct=1
for i in range(n-1):
  if l[i]<l[i+1]:
    ct+=1
  else:
    ans.append(ct)
    ct=1
ans.append(ct)
ct=1
print(n-max(ans))

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

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

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

p = 0
pre = -1
k = 0
for i in ind:
    if i > pre:
        k += 1
    else:
        k = 1
    p = max(p, k)
    pre = i

print(N-p)

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

cnt=0
maxcnt=0


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

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

print(n-maxcnt-1)

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

idx = [-1 for _ in range(N)]
successive = [False for _ in range(N)]

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

for p in P:
    if p < N-1 and idx[p+1] > idx[p]:
        successive[p] = True

cnt = 1
max_cnt = 0
for p in range(N):
    if successive[p]:
        cnt += 1
    else:
        max_cnt = max(cnt, max_cnt)
        cnt = 1

print(N-max_cnt)

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

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


max_length = 1

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

print(N - max_length)

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

memo = {}
for i in range(n):
    memo[a[i]] = i
ans = 0
pos = -1
cnt = 0
for i in range(n):
    if pos < memo[i+1]:
        cnt += 1
        pos = memo[i+1]
    else:
        ans = max(ans, cnt)
        cnt = 1
        pos = memo[i+1]
print(n - max(ans, cnt))

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

memo = {}
for i in range(n):
    memo[a[i]] = i
ans = 0
pos = -1
cnt = 0
for i in range(n):
    if pos < memo[i+1]:
        cnt += 1
        pos = memo[i+1]
    else:
        ans = max(ans, cnt)
        cnt = 1
        pos = memo[i+1]
print(n - max(ans, cnt))

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

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


c = 0
ans = 0
for i in range(1, N+1):
    if V[i-1] > V[i]:
        c = 1
    else:
        c += 1
    ans = max(c, ans)

print(N-ans)

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

def main():
    N = int(input())
    ind = [0 for _ in range(N)]
    for i in range(N):
        A = int(input())
        ind[A-1] = i

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

    print(N-ans-1) 

if __name__ == "__main__":
    main()

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = [I() for _ in range(n)]
inde = [0]*n
for i in range(n):
    inde[p[i]-1] = i
cnt = 1
ans = 0
for i in range(1,n):
    if inde[i-1] < inde[i]:
        cnt += 1
    else:
        ans = max(ans,cnt)
        cnt = 1
ans = max(ans,cnt)
ans = n - ans
print(ans)

Solution (Python):
n=int(input())
import collections
D=collections.defaultdict(int)
for i in range(n):
  p=int(input())
  D[p]=D[p-1]+1
print(n-max(list(D.values())))

Solution (Python):
n=int(input())
l=[0]*n
for i in range(n):
    a=int(input())
    l[a-1]=i
cnt=1;ans=0
for i in range(1,n):
    if l[i-1]>l[i]:
        if cnt>ans:ans=cnt
        cnt=1
        continue
    cnt+=1
print(n-ans if ans!=0 else 0)

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
vi = {v: i for i, v in enumerate(P)}
incmax = inc = 1
before = vi[1]
for v in range(2, N + 1):
    if vi[v] > before:
        inc += 1
    else:
        inc = 1
    incmax = max(incmax, inc)
    before = vi[v]
print(N - incmax)

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

Solution (Python):

def main():
    N, *P = map(int, open(0).read().split())
    
    dp = [0] * (N + 1)
    for i in P:
        dp[i] = dp[i - 1] + 1
    ans = N - max(dp)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    N, *P = map(int, open(0))
    dp = [0] * (N + 1)
    for i in P:
        dp[i] = dp[i - 1] + 1
    ans = N - max(dp)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, *P = map(int, open(0))

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

print(N - ma)

Solution (Python):
N, *P = map(int, open(0))

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

print(N - max(dp))

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


res = 1
now = 1
for i in range(1,n):
    if data[i-1] < data[i]:
        now += 1
    else:
        now = 1
    res = max(res,now)

print(n-res)

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
    
ans =  N - max(dp)
print(ans)

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

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

Solution (Python):
n = int(input())
a_list = [0 for _ in range(n)]
for i in range(n):    
    a_list[int(input()) - 1] = i
length = 1
ans = 0
prev = a_list[0]
for i in range(n - 1):
    if (a_list[i + 1] - prev) >= 1:
        length += 1
    else:
        ans = max(length, ans)
        length = 1
    prev = a_list[i + 1]
ans = max(length, ans)
print(n - ans)

Solution (Python):
n = int(input())
l = [int(input()) for _ in range(n)]
q = [0]*n
for i in range(n):
  q[l[i]-1] = i
a = 1
ans = 0
for i in range(1,n):
  if q[i]>q[i-1]:
    a += 1
  else:
    ans = max(ans,a)
    a = 1
print(n-max(ans,a))

Solution (Python):


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

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

k = 1
i = 1
while i < N:
    cnt = 0
    while(i < N and Q[i-1] < Q[i]):
        cnt += 1
        i += 1
    k = max(k, cnt+1)
    i += 1

print(N - k)

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    P = [0] * N
    index = [0] * (N + 1)

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

    length = 1
    seq = 1
    for i in range(1, N):
        if index[i] < index[i + 1]:
            seq += 1
        else:
            length = max(length, seq)
            seq = 1
            
    length = max(length, seq)

    print(N - length)

sol()

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    P = [0] * N

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

    pToIndex = {p : i for i, p in enumerate(P)}

    maxLeng = 1
    length = 1
    for n in range(1, N):
        if pToIndex[n] < pToIndex[n + 1]:
            length += 1
            maxLeng = max(maxLeng, length)
        else:
            length = 1

    print(N - maxLeng)

sol()

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





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

p_to_i = {x:i for i,x in enumerate(P)}

max_rest = 1

x = 1
for n in range(2,N+1):
    if p_to_i[n] > p_to_i[n-1]:
        x += 1
        if max_rest < x:
            max_rest = x
    else:
        x = 1

answer = N - max_rest
print(answer)

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
P = [int(sys.stdin.readline()) for _ in range(N)]


dp = np.zeros(N + 1, dtype=int)
for i in range(N):
    p = P[i]
    dp[p] = dp[p - 1] + 1
print(N - dp.max())

Solution (Python):
N = int(input())
a = [0]*N
b = [0]*N
for i in range(N):
    P = int(input()) - 1
    a[i] = P
    b[P] = i
c = 1
m = 1
for i in range(1,N):
    if b[i] > b[i-1]:
        c += 1
        if c > m:
            m = c
    else:
        c = 1
print(N-m)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())

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

T = [0]*(N-1)

E = [0]*N

for i in range(N):
    E[P[i]-1] = 1
    if P[i]<N:
        if E[P[i]]==1:
            T[P[i]-1] = 1

max_score = 0
prev = -1

for i in range(N-1):
    if T[i]==1:
        max_score=max(max_score,i-prev)
        prev = i

max_score = max(max_score,N-1-prev)

print(N-max_score)

Solution (Python):
N=int(input())
P=[int(input()) for i in range(N)]
pos=[-1]*N
for i,p in enumerate(P):
    pos[p-1]=i
x,mx=0,0
for i in range(N-1):
    if pos[i]<pos[i+1]:
        x+=1
        mx=max(mx,x)
    else:
        x=0
print(N-mx-1)

Solution (Python):
N = int(input())
P = [int(input()) for _ in [0]*N]
m = [0]*N
for i,p in enumerate(P): m[p-1] = i
ans = 0
c = 0
j=-1
for i in m:
    c = (c+1) if j<i else 1
    j=i
    ans = max(ans,c)
print(N-ans)

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

dp = [0]*(N+1)

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

ans = N - max(dp)

print(ans)

Solution (Python):
n = int(input())
p = []
l = [0]*n
count = 0
for i in range(n):
    count = count + 1
    p1 = int(input())
    p.append(p1)
    l[p1-1] = count
count1 = 1
l2 = [1]
for i in range(n-1):
    if l[i] <  l[i+1]:
        count1 = count1 + 1
        l2.append(count1)
    else:
        count1 = 1
print(n-max(l2))

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

seq = 0
seq_max = 0
prev = 0
for i in range(1, N+1):
    if place[i] >= prev:
        seq += 1
    else:
        seq = 1
    prev = place[i]
    seq_max = max(seq, seq_max)
print(N - seq_max)

Solution (Python):
n=int(input())
arr=[int(input()) for _ in range(n)]
pos=[0]*(n+1)
for i in range(n):
  pos[arr[i]]=i
cnt=[0]*(n+1)
cnt[1]=1
for i in range(2,n+1):
  if pos[i-1]<pos[i]:
    cnt[i]=cnt[i-1]+1
  else:
    cnt[i]=1
print(n-max(cnt))

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

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

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

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

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


if __name__ == "__main__":
    main()

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


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
p = [int(input()) for _ in range(n)]
id = [0 for _ in range(n)]
for i in range(n):
    id[p[i]-1] = i
cnt = 0
l = r = 0
while l < n:
    while r < n-1 and id[r] < id[r+1]:
        r += 1
    cnt = max(cnt, r-l+1)
    if r == l:
        r += 1
    l = r
print(n-cnt)

Solution (Python):
from functools import reduce


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

INF = 10**15


Q = {p: i for i, p in enumerate(P, 1)}


ans, _ = reduce(
    lambda acc, j: (
        min(
            acc[0],
            acc[1] + N - j + 1
        ),
        acc[1] if j > N or Q[j - 1] < Q[j] else
        j - 1
    ),
    range(2, N + 2),
    (INF, 0)
)


print(ans)

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

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

longest_increasing_subsequence = [0]*(N+1) 

for p in P:
  longest_increasing_subsequence[p] = max(1, longest_increasing_subsequence[p-1]+1)


print(N - max(longest_increasing_subsequence))

Solution (Python):
n = int(input())
p_index = [0] * n
for i in range(n):
    p_index[int(input())-1] = i
prev = 10**9
ans = 0
val = 1
for item in p_index:
    if prev > item:
        val = 1
    else:
        val += 1
    prev = item
    ans = max(ans, val)
print(n-ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)
ans = 0
tmp = 0
inf = 10 ** 20
INF = float("INF")
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hip(n): return [i() - 1 for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
p = hip(n)

stillset = set()
flagli = [0] * n
for i in range(n):
    if p[i] - 1 in stillset:
        if p[i] != 0:
            flagli[p[i] - 1] = 1
    stillset.add(p[i])

sign = 1 if flagli[0] == 1 else 0
tmp = 1 if flagli[0] == 1 else 0
for i in range(1, n):
    if sign == 1:
        if flagli[i] == 1:
            tmp += 1
        else:
            sign = 0
            ans = max(ans, tmp)
            tmp = 0
    else:
        if flagli[i] == 1:
            tmp += 1
            sign = 1
        else:
            pass
ans = max(ans, tmp) + 1

print(n - ans)

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

k = 1
tmpk = 1
for i in range(1, n):
  if pn[i-1] < pn[i]:
    tmpk += 1
  else:
    k = k if k > tmpk else tmpk
    tmpk = 1

k = k if k > tmpk else tmpk
print(n - k)

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

Solution (Python):
N = int(input())
ps = []
for i in range(N):
    ps.append(int(input()))
memo = {}
for i,p in enumerate(ps):
    memo[p] = 0
    if p-1 in memo:
        memo[p-1] = 1

dct = sorted(memo.items())
result = 0
c = 0
for k,v in dct:
    if v == 1:
        c += 1
    else:
        if c > result:
            result = c
        c = 0
print(N-result-1)

Solution (Python):
import bisect

N=int(input())

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


L=[0 for i in range(N+1)]

for i in range(N):
    if L[A[i]-1]>0:
        L[A[i]]=(L[A[i]-1]+1)
    else:
        L[A[i]]=1
print(N-max(L))

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

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

dp = [1]*(n+1)
for i in range(n):
    if d[i+1] > d[i]:
        dp[i+1] = dp[i] + 1
print(n - max(dp))

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

Solution (Python):
N = int(input())
L = []
for i in range(N):
  L.append(int(input()))
TF = [False]*(N+1)
dp = [0]*(N+1)
for i in range(N):
  TF[L[i]] = True
  if TF[L[i]-1] == True:
    dp[L[i]] = dp[L[i]-1]+1
print(N-max(dp)-1)

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

T = [0] * (N + 1)
for i in P:
  if T[i - 1] == 0:
    T[i] = -1
  elif T[i - 1] < 0:
    T[i - 1] -= 1
    T[i] = i - 1
  else:
    T[T[i - 1]] -= 1
    T[i] = T[i - 1]

print(N + min(T))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

for a in A:
    dp[a] += dp[a-1]+1
print(N-max(dp))

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

d = {pi: i for i, pi in enumerate(p)}
idx = -1
count = 0
ma = 0

for i in range(1, n+1):
    if d[i] > idx:
        count += 1
        idx = d[i]
    else:
        ma = max(ma, count)
        idx = d[i]
        count = 1

ma = max(ma, count)
print(n - ma)

Solution (Python):


import sys

INF = float('inf')
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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    P = [II() for _ in range(n)]

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

    return n - max(dp)


print(main())

Solution (Python):


import sys

INF = float('inf')
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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    P = [II() for _ in range(n)]

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

    return n - max(dp)


print(main())

Solution (Python):
from functools import reduce


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

INF = 10**15


Q = {p: i for i, p in enumerate(P, 1)}


ans = reduce(
    lambda acc, j: (
        min(
            acc[0],
            acc[1] + N - j + 1
        ),
        acc[1] if j > N or Q[j - 1] < Q[j] else
        j - 1
    ),
    range(2, N + 2),
    (INF, 0)
)[0]


print(ans)

Solution (Python):
from functools import reduce


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

INF = 10**15


Q = {p: i for i, p in enumerate(P, 1)}


ans = reduce(
    lambda acc, j: (
        min(
            acc[0],
            acc[1] + N - j + 1
        ),
        acc[1] if j > N or Q[j - 1] < Q[j] else
        j - 1
    ),
    range(2, N + 2),
    (INF, 0)
)[0] if N >= 2 else 0


print(ans)

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

Solution (Python):




import numpy as np 





import os


import sys


sys.setrecursionlimit(1000000)
'''
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  
print(sorted(a, key=itemgetter(0)))  
print(sorted(a, key=itemgetter(0, 2)))  
print(sorted(a, key=lambda x: x[0] * x[2]))  
print(sorted(a, reverse=True))  
a.sort()  
'''

test_data1 = '''\
8
6
3
1
2
7
4
8
5
'''

test_data2 = '''\
6
3
2
5
1
4
6
'''

test_data3 = '''\
4
1
3
2
4
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        
        
        
        n=int(f.readline())
        p=[0]*n
        for i in range(n):
            p[i]=int(f.readline())
        
else:
    n=int(input())
    p=[0]*n
    for i in range(n):
        p[i]=int(input())
    

a=[0]*n
cnt=1
ans=0
for i in range(n):
    a[p[i]-1]=i

for i in range(n):
    if i==0:
        pre=a[0]
    else:
        if a[i]>pre:
            cnt+=1
        else:
            ans=max(ans,cnt)
            cnt=1
    ans=max(ans,cnt)
    pre=a[i]
print(n-ans)

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

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

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

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

p = [0] * n

for i in range(n):
    if a[i] == 1:
        p[0] = 1
        continue
    if p[a[i] - 2] == 0:
        p[a[i] - 1] = 1
    else:
        p[a[i] - 1] = p[a[i] - 2] + 1
print(n - max(p))

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


Q = sorted([(p, i) for i, p in enumerate(P, start=1)])
Q = [i for p, i in Q]

dp = [1] * (N + 1)
for i in range(1, N):
    if Q[i] > Q[i - 1]:
        dp[i] = dp[i - 1] + 1

print(N - max(dp))

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

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

Solution (Python):
N = int(input())
P = [int(input()) for _ in range(N)]
Index = [None] * N
Used = set()
Chain = [1] * N

for i in range(N):
    p = P[i]
    Index[p-1] = i
    Used |= {p}
    if p-1 in Used:
        Chain[i] = Chain[Index[p-2]] + 1

print(N - max(Chain))

Solution (Python):
n = int(input())
p = [int(input()) for _ in range(n)]
p_m = [0]*n
for i,j in enumerate(p):
    p_m[j-1] = i
res = -10**9
cnt = 0
prev = -1
for i in p_m:
    if prev <= i:
        cnt += 1
        prev = i
    else:
        res = max(res, cnt)
        cnt = 1
        prev = i
else:
    res = max(res, cnt)
print(n - res)

Solution (Python):
n = int(input())
p = [int(input()) for _ in range(n)]
q = [-1] * n
for i, j in enumerate(p):
    q[j - 1] = i
res = n
tmp = 1
for i, j in zip(q, q[1:]):
    if i < j:
        tmp += 1
    else:
        res = min(res, n - tmp)
        tmp = 1
else:
    res = min(res, n - tmp)
print(res)

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

counter = [0] * (N + 1)

for p in Ps:
    counter[p] = counter[p-1] + 1

ans = 0
for c in counter:
    ans = max(ans, c)
print(N - ans)

Solution (Python):
N=int(input())
if N==1:
  print(0)
  exit()
a=[0]*N
for i in range(N):
  m=int(input())
  a[m-1]=i
ans=0
for i in range(N):
  if i==0:
    s,l=-1,1
  elif i==N-1:
    if s<a[i]:
      l+=1
      ans=max(ans,l)
    else:
      ans=max(ans,l)
      l=1
  else:
    if s<a[i]:
      l+=1
    else:
      ans=max(ans,l)
      l=1
  s=a[i]
print(N-ans)

Solution (Python):
N = int(input())
St = [0 for _ in range(N+1)]
for _ in range(N):
   i = int(input()) 
   St[i] = max(St[i-1]+1, 1)
print(N-max(St))

Solution (Python):

from sys import stdin

s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


N = d_in()

aranged_list = [0] * N
for i in range(N):
    idx = d_in()
    aranged_list[idx-1] = i

ans, count = 0, 0
temp = -1
for i in aranged_list:
    if i > temp:
        count += 1
        temp = i
    else:
        ans = max(ans, count)
        count = 1
        temp = i
ans = max(ans, count)

print(N - ans)

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

Solution (Python):
import sys

x = input()
d = {}
result = 0

for line in sys.stdin:
    n, = line.strip().split(" ")
    n = int(n)
    if n-1 in d:
        d[n] = d[n-1] + 1
    else:
        d[n] = 1
    result = max(d[n], result)

print(int(x) - result)

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

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

ans = 0
i = 0
temp = 1
while i < n-1:
    if q[i] > q[i+1]:
        if temp > ans:
            ans = temp
        temp = 1
    else:
        temp += 1
    i += 1
if temp > ans:
    ans = temp
print(n-ans)

Solution (Python):
N = int(input())
chain = [0 for i in range(N+1)]
for i in range(N):
  a = int(input())
  chain[a] = chain[a-1]+1
print(N-max(chain))

Solution (Python):
N = int(input())
a = [0 for i in range(N)]
chain = [0 for i in range(N+1)]
for i in range(N):
  a[i] = int(input())
  chain[a[i]] = chain[a[i]-1]+1
print(N-max(chain))

Solution (Python):
import sys
from collections import Counter
N = int(input())
counter = Counter()
for n in map(int, sys.stdin):
    counter[n] = counter[n-1]+1

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

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

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

import sys
if n == 1:
    print(0)
    sys.exit()

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

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

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

stay_num_cnt = 0
cnt = 0
t = 0
for x in q:
    if x >= t:
        cnt += 1
    else:
        cnt = 1
    t = x
    stay_num_cnt = max(stay_num_cnt, cnt)
print(n - stay_num_cnt)

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

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n = ni()
p = []

for _ in range(n):
    p.append(ni())

dp = [0]*(n+1)

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

print(n - max(dp))

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

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n = ni()
p = []
idx = [0]*(n+1)

for _ in range(n):
    p.append(ni())

for i,pi in enumerate(p):
    idx[pi] = i+1

con = [0]*(n+1)
con[1] = 1
for i in range(1,n):
    if idx[i] < idx[i+1]:
        con[i+1] = con[i] + 1
    else:
        con[i+1] = 1
        
print(n - max(con))

Solution (Python):
import sys
N = int(input())
dp = [0] * (N + 1)
for x in map(int, sys.stdin):
    dp[x] = dp[x - 1] + 1
print(N - max(dp))

Solution (Python):
N = int(input())
idx = {int(input()): i for i in range(N)}
res = N - 1
cnt = 1
for x in range(2, N + 1):
    if idx[x - 1] < idx[x]:
        cnt += 1
    else:
        res = min(res, N - cnt)
        cnt = 1
print(min(res, N - cnt))

Solution (Python):
import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    N = int(input_raw[0])
    Q = [0 for i in range(N + 1)]
    count = 0
    for i in range(N):
        input_raw = read_func().strip().split()
        Q[int(input_raw[0])] = i

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

    print N - max_count


if __name__ == '__main__':
    main()

Solution (Python):
ip=lambda:int(input())
n=ip()
p=[ip() for _ in range(n)]
d=[0]*(n+1)
for q in p:
  d[q]+=d[q-1]+1
print(n-max(d))

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)