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



Sample input:
4
1
3
2
4


Sample output:
2

Submission status: Accepted

Solution code:
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
#main code here!
    
    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()

Submission status: Accepted

Solution code:
def agc024_b():
    n = int(input())
    P = [int(input())-1 for _ in range(n)]  # 0 .. n-1 にしておく
    if n == 1: return print(0)

    A = [0]*n  # 登場するindex
    for i, p in enumerate(P):
        A[p] = i

    cnt = 0  # iの登場順がi-1より後ろが連続する回数
    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()

Submission status: Accepted

Solution code:
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(i+1,ans)


print(n-ans)

Submission status: Accepted

Solution code:


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())

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

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

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()))


# ===CODE===


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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()))

Submission status: Accepted

Solution code:
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

# Qの最大連続増加部分列の長さを求める

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)

Submission status: Accepted

Solution code:
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  # indexの値が単調増加になるような最長の列長
    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()

Submission status: Accepted

Solution code:
#

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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

#############
# Main Code #
#############

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
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)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    P = list(int(input()) for _ in range(N))
    dp = [0]*(N+1)   #dp[i]:１づつ増加する部分列の最大の数字がiとなるものの最大長さ

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

    print(N - ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
"""
連続する数は動かさず、それ以外を左右に分配していく
⇨並べ替えた後、昇順に連続しているかは、インデックスが昇順になっているかを見る
"""
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILs(N)

START = []
f = [0 for i in range(N+1)]
for a in A:
  if f[a-1] == 0:
    START.append(a)
    f[a] = 1
  else:
    f[a] = 1
START.sort()
dic = {k:[] for k in START}
for a in A:
  p = bisect.bisect(START,a)
  dic[START[p-1]].append(a)
print(N-max(len(dic[k]) for k in START))

Submission status: Accepted

Solution code:
n=int(input())
p=[int(input()) for _ in range(n)]
d={}
for pi in p:
  if pi-1 in d:
    d[pi]=d[pi-1]+1
  else:
    d[pi]=1
print(n-max(d.values()))

Submission status: Accepted

Solution code:
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))

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n=int(input())
P=[int(input()) for _ in range(n)]
DP=[0 for _ in range(n+1)]

for i in P:
    DP[i]=DP[i-1]+1
print(n-max(DP))

Submission status: Accepted

Solution code:
n=int(input())
P=[int(input()) for _ in range(n)]
DP=[0]*(n+1)
for i in P:
    DP[i]=DP[i-1]+1
print(n-max(DP))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
p = [0 for _ in range(N)]
for i in range(N):
  A[i] -= 1
  p[A[i]] = i
m = 0
prev = -1
cnt = 0
for i in range(N):
  if p[i] > prev:
    cnt += 1
  else:
    m = max(m, cnt)
    cnt = 1
  prev = p[i]
m = max(m, cnt)
print(N-m)

Submission status: Accepted

Solution code:
#pdf見た
n = int(input())
q = [0]*n
for i in range(n):
    p = int(input())-1
    q[p] = i
    
s=f=0
c = set()
for i in range(1,n):
    if q[i]<q[i-1]:
        f=i-1
        c.add(f-s+1)
        s=i
if c==set():
    print(0)
else:
    print(n-max(c))

Submission status: Accepted

Solution code:
N = int(input())
S = [0]*N
for i in range(N):
    a = int(input())
    a -= 1
    if a == 0:
        S[0] = 1
    else:
        if S[a-1] == 0:
            S[a] = 1
        else:
            S[a] = S[a-1] + 1
print(N-max(S))

Submission status: Accepted

Solution code:
n = int(input())
pl = [int(input()) for _ in range(n)]

d = {}
for i in range(n):
    d[pl[i]] = i

dp = [1]*n
p = 1
while p<n:
    if d[p+1]>d[p]:
        dp[d[p+1]] = dp[d[p]]+1
    p += 1
print(n-max(dp))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
pl = [-1]*(n+1)

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
p = list(map(int,read().split()))
q = [0] * n
for i,p_i in enumerate(p):
    q[p_i-1] = i

longest = 1
now = 1
for i in range(1,n):
    if(q[i] > q[i-1]):
        now += 1
    else:
        now = 1
    longest = max(longest,now)

print(n-longest)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
p = [[int(j),i] for i,j in enumerate(read().split()) ]
p.sort()

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

print(n-longest)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  lp = [int(input()) for _ in range(n)]
  ilp = sorted(enumerate(lp), key=lambda x:x[1])
  max_cnt = 0
  cnt = 1
  for i in range(n-1):
    if ilp[i] < ilp[i+1]:
      cnt += 1
    else:
      max_cnt = max(max_cnt, cnt)
      cnt = 1
  print(n - max(max_cnt, cnt))
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect
 
n = int(input())
cou = [0 for i in range(n+1)]
for i in range(n):
    now = int(input())
    cou[now] = cou[now-1] + 1  

print(n-max(cou))

Submission status: Accepted

Solution code:
n=int(input())
l=[0]*n
for i in range(n):
    l[int(input())-1]=i
pre=-1
now=0
ans=n
for i in l:
    if pre<i:
        now+=1
    else:
        ans=min(ans,n-now)
        now=1
    pre=i

print(min(ans,n-now))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc024/tasks/agc024_b

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

ans = 0
res = 1
for i in range(1, N):
    if Q[i] > Q[i - 1]:
        # keepできる
        res += 1
    else:
        # 回数をカウント
        ans = max(ans, res)
        res = 1
ans = max(ans, res)
# 全体 - 動かさない
print(N - ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import io, os
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
def input():
    return sys.stdin.readline()[:-1]
def main():
    n = int(input())
    a = [int(input()) for k in range(n)]
    b = [[a[k],k] for k in range(n)]
    b = sorted(b)
    c = [b[k][1] for k in range(n)]
    c = [-1] + c + [100000]
    t = 0
    ans = 0
    for k in range(1,n+1):
        if c[k-1] < c[k]:
            t += 1
        else:
            t = 1
        ans = max(ans,t)
    print(n-ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
P = [int(input()) for i in range(N)]
is_earlier = [True] * N
appeared = set()
appeared.add(N+1)
for p in P:
  if p+1 in appeared:
    is_earlier[p-1] = False
  appeared.add(p)

M = 0
now = 1
for i in range(N):
    if is_earlier[i]:
        now += 1
    else:
        M = max(M, now)
        now = 1

print(N - M)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    P = []
    for i in range(N):
        P.append((int(input()), i))
    P.sort(key=lambda x: x[0])
    Q = list(zip(*P))[1]
    cnt = 1; ans = 1
    for i in range(N-1):
        if Q[i] < Q[i+1]:
            cnt += 1
        else:
            cnt = 1
        ans = max(ans, cnt)
    print(N-ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
from collections import Counter
dp=[0]*(n+1)
for x in a:
    if x!=1 and dp[x-1]!=0:
        dp[x]=dp[x-1]
    elif x!=1:
        dp[x]=x
    else:
        dp[1]=1

c=Counter(dp)
_, most=c.most_common()[0]

print(n-most)

Submission status: Accepted

Solution code:

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
#print('n,p=',n,p,a)
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)

Submission status: Accepted

Solution code:
n = int(input())
p = []
for _ in range(n):
    p.append(int(input()))
li = [0]*(n+1)
for i in p:
    li[i] = li[i-1]+1
print(n-max(li))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
# dbg = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

N = ini()
P = list(map(int, sys.stdin.readlines()))
INF = 1 << 40


def solve():
    if N == 1:
        return 0

    inds = [None] * (N + 1)
    for i, x in enumerate(P):
        inds[x] = i

    streak = [1] * (N + 1)
    for k in range(2, N + 1):
        if inds[k - 1] < inds[k]:
            streak[k] = streak[k - 1] + 1
    ans = INF
    for k in range(2, N + 1):
        r = 0 if k == P[-1] else 1
        r += N - k
        l = (k - 1) - streak[k - 1]
        if ans > l + r:
            ans = l + r
        # dbg(f"{ans=} {l=} {r=}")
    return ans


print(solve())

Submission status: Accepted

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

check = [0]*(N+1)
for i in range(N):
    X = P[i]
    check[X] = check[X-1]+1
M = max(check)
print(N-M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
p=[int(input())-1 for _ in range(n)]
a=[0]*n
for i in range(n):
    a[p[i]]=i
l=1
ans=1
for i in range(n-1):
    if a[i]<a[i+1]:
        l+=1
    else:
        ans=max(ans,l)
        l=1
ans=max(ans,l)
print(n-ans)