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:
# coding: utf-8
import re
import math
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="number"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True

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

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

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

Submission status: Accepted

Solution code:
N=int(input())

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


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

print(N-max_con)

Submission status: Accepted

Solution code:
#N, *a = map(int, open(0).read().split())
def main():
    N = int(input())
    a=[]
    for i in range(N):
        a.append(int(input()))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

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

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

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

Submission status: Accepted

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

import sys

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

N = INT()
A = LIST(N)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

S = [0]*(N+1)

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

print(N-max(S))

Submission status: Accepted

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

S = [0]*(N+1)

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

print(N-max(S))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

LIS = [0] * (N + 1)

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

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

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = int(input())

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

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



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

print(N - max_cnt)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])


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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

answer = n - ans - 1
print(answer)

Submission status: Accepted

Solution code:
import sys

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

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

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

print(N-max(dp))
#40

Submission status: Accepted

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    examB()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
read = sys.stdin.read

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

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

length.append(cnt)

print(N - max(length))

Submission status: Accepted

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

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

ans = N - max(dp)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

#print(sor)

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

print(n - count - 1)

Submission status: Accepted

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

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

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

print(n - ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

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

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

	ans = N - ans_pre
	print(N - ans_pre)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
n = int(input())
p = [int(input()) for i in range(n)]
f = [0]*(n+1)
m = [n-1]*(n+1)
for i in p:
    if f[i-1]:
        m[i] = m[i-1]-1
    f[i] = 1
print(min(m))

Submission status: Accepted

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

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

count = 1
i = 1
while i < N: #startを動かす
    tmp = i
    # print ('tmp', tmp)
    tmp_count = 1
    while tmp < N and lst[tmp] < lst[tmp + 1]:
        tmp_count += 1
        tmp += 1
    count = max(count, tmp_count)
    i = tmp + 1

print (N - count)
# print (lst)

Submission status: Accepted

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


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

    # See:
    # https://www.youtube.com/watch?v=S1IkBhwnuYU
    # KeyInsight
    # 取り出した部分列が昇順かつ連続した数字が並んでいるかどうか

    # ■できた部分
    # N - 部分列の長さの最大値が答え

    # ■できなかった部分
    # 判定方法：
    # piの値が並び替え前にどこに位置しているかをメモ
    # 昇順かつ連続して並んでいる部分列の長さを数える
    p = [0 for _ in range(n)]

    # See:
    # https://atcoder.jp/contests/agc024/submissions/2532965
    for i in range(n):
        x = int(input())
        x -= 1
        p[x] = i

    len_max = 1
    count = 1

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

        # WAが取れなかった原因：部分列の最大値の更新ができていない場合があった
        # 例：すべて昇順に並んでいる
        len_max = max(len_max, count)

    print(n - len_max)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

    # See:
    # https://www.youtube.com/watch?v=S1IkBhwnuYU
    # KeyInsight
    # 取り出した部分列が昇順かつ連続した数字が並んでいるかどうか

    # ■できた部分
    # N - 部分列の長さの最大値が答え

    # ■できなかった部分
    # 判定方法：
    # piの値が並び替え前にどこに位置しているかをメモ
    # 昇順かつ連続して並んでいる部分列の長さを数える
    p = [0 for _ in range(n)]

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

    len_max = 1
    count = 1

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

        len_max = max(len_max, count)

    print(n - len_max)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

lis = [0] * (N+1)

for i in range(N):

    P = int(input())

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

print (N - max(lis))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

#################

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

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

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

if max_ascend<temp:
    max_ascend = temp

print(N-max_ascend)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

    print(N - max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

succ = [1] * n

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

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

print(n-max(succ))

Submission status: Accepted

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

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

Submission status: Accepted

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


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

"""
idxs = [0] * (N+1)
for i in range(N):
    idxs[P[i]] = i # それぞれの数字の場所を記録

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

print(N - max_len)

Submission status: Accepted

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

Submission status: Accepted

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


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


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



print(n - max(LIS))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

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

    # Q[i]: P[i] から左を見たとき、1ずつ増加して昇順にある要素の数
    Q = [0]*(N+1)
    for p in P:
        Q[p] = Q[p-1] + 1 # p-1 だけを見ればよい

    print(N-max(Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

count = [0 for i in range(N)]
now = [-1 for i in range(N+1)]
for i in range(N):
    if P[i] == 1:
        now[P[i]-1] = P[i]
        count[P[i]-1]+=1
    elif now[P[i]-2] == -1:
        now[P[i]-1] = P[i]
        count[P[i]-1]+=1
    else:
        now[P[i]-1] = P[i]
        count[P[i]-1] = count[P[i]-2]+1
        
#print(count,now)
MAX = max(count)
ans = N-MAX
print(ans)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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)

Submission status: Accepted

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