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:
from collections import defaultdict
n = int(input())
p = [int(input()) for i in range(n)]
d = defaultdict(int)
for i in p:
    d[i] = d[i - 1] + 1
print(n - max(d.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

c = defaultdict(int)
for Pi in P:
    c[Pi] = c[Pi - 1] + 1

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    P = list(int(input()) for _ in range(N))
    
    dp = [0] * (N + 1)
    for i in range(N-1,-1,-1):
        if P[i] == N:
            dp[P[i]] = 1
            continue
        if dp[P[i] + 1] == 0:
            dp[P[i]] = 1
        else:
            dp[P[i]] = dp[P[i] + 1] + 1
    print(N - max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

#dp[i]はiで終わる連続整数長
dp = [0 for _ in range(n+1)]
for i in range(n):
    dp[p[i]] = dp[p[i] - 1] + 1

print(n - max(dp))

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    p = []
    for _ in range(N): p.append(int(input()))

    d = dict()
    for i in range(N):
        if i == 0:
            d[p[i]] = 1
        else:
            if p[i] - 1 in d:
                d[p[i]] = d[p[i]-1] + 1
            else:
                d[p[i]] = 1
    return N - max(list(d.values()))


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

Submission status: Accepted

Solution code:
n = int(input())
li = [int(input()) for _ in range(n)]
ma = {}
for i,l in enumerate(li):
    ma[l] = i+1
nu = []
for j in range(n):
    nu.append(ma[j+1])

ans = [0]
tmp = 0
cnt = 0
for k,u in enumerate(nu):
    if k == 0:
        tmp = u
        cnt += 1
        continue
    if u > tmp:
        tmp = u
        cnt += 1
    else:
        ans.append(cnt)
        tmp = u
        cnt = 1
ans.append(cnt)
#print(ans)
#print(n,max(ans))
print(n - max(ans))

Submission status: Accepted

Solution code:
n = int(input())

p = []
for _ in range(n):
    p.append(int(input()))
    
ans = [0 for _ in range(n + 1)]
for num in p:
    ans[num] = ans[num - 1] + 1
print(n - max(ans))

Submission status: Accepted

Solution code:
n = int(input())

count = [0]*(n+1)
P = map(int, (input() for _ in range(n)))
for p in P:
    count[p]=count[p-1]+1    

print(n - max(count))

Submission status: Accepted

Solution code:
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
chain_length = [-1 for i in range(n+1)]
for i in p:
    if chain_length[i-1] < 0:
        chain_length[i] = 1
    else:
        chain_length[i] = chain_length[i-1] + 1
print(n - max(chain_length))

Submission status: Accepted

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

visit = [-1 for _i in range(n+1)]
for i in p:
    if visit[i-1] < 0:
        visit[i] = 1
    else:
        visit[i] = visit[i-1]+1
print(n-max(visit))

Submission status: Accepted

Solution code:
n = int(input())
c = [int(input()) for i in range(n)]
s = [0]*n
for i,ci in enumerate(c):
  s[ci-1] = i
cnt = 1
ans = n-1
for i in range(n-1):
  if s[i] < s[i+1]:
    cnt += 1
  else:
    ans = min(n-cnt,ans)
    cnt = 1
ans = min(n-cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

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


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


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

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

    # 数が連続する増加部分数列の最大の長さを調べる
    # ある数字pが右端となる時の部分数列の最大の長さを保持
    max_len = 1
    tmp = 1
    for p in range(2, N + 1):
        if p2idx[p] > p2idx[p - 1]:
            tmp += 1
            if max_len < tmp:
                max_len = tmp
        else:
            tmp = 1

    print(N - max_len)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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


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


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

    # dp[i] := i が一番右端に来るときの最大長
    dp = [0] * (N + 1)
    for i in range(N):
        p = P[i]
        dp[p] = dp[p - 1] + 1

    print(N - max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = n - max(dp[1:])
print(ans)

Submission status: Accepted

Solution code:
#AGC024-B Backfront
"""
ある一要素を選んで数列の先頭もしくは最後尾に移動させる。
これを繰り返して昇順に並び替えるときの最小手数
解法：
O(N)で求める必要があるので、シュミレーション的な解法ではない。
増加部分列のうち、その増加分が1である制約を加えた場合の
部分列の長さをlとした時、
n-lが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline())-1)

lst2 = [0]*n
for i in range(n):
    lst2[lst1[i]] = i 
#lst2にlst1でのindex(場所)を保存した場合、
#左右の２要素について、右の要素が左より大きければ、
#その2要素については連続でその昇順に存在していることがわかる
#print(lst1)
#print(lst2)

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

ans = max(ans,res)
print(n-ans)

Submission status: Accepted

Solution code:
#AGC024-B Backfront
"""
ある一要素を選んで数列の先頭もしくは最後尾に移動させる。
これを繰り返して昇順に並び替えるときの最小手数
解法：
O(N)で求める必要があるので、シュミレーション的な解法ではない。
増加部分列のうち、その増加分が1である制約を加えた場合の
部分列の長さをlとした時、
n-lが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline())-1)

lst2 = [0]*n
for i in range(n):
    lst2[lst1[i]] = i
#print(lst1)
#print(lst2)

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

ans = max(ans,res)
print(n-ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
l=[0]*N
for i in range(N):
    n=int(input())-1
    l[n]=i
a=0
t=1
for i in range(N-1):
    if l[i]<l[i+1]:
        t+=1
    else:
        if a<t:
            a=t
        t=1
if a<t:
    a=t
print(N-a)

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for _ in range(n)]
pi = [(x-1, i) for i, x in enumerate(p)]
pi.sort()
pi.append((n, -1))

l, mxl = 0, 0
for i, x in pi:
    if x < pi[i-1][1]:
        mxl = max(l, mxl)
        l = 0
    l += 1

print(n - mxl)

Submission status: Accepted

Solution code:
n = int(input())
cn = [0 for i in range(n+1)]
for i in range(n):
    p = int(input())
    cn[p] = cn[p-1]+1

print(n-max(cn))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#backfront
N=int(input())
lists=[]
for _ in range(N):
    x=int(input())
    lists.append((_,x))
lists.sort(key=lambda x:x[1])
lists.append((-10000000000000000,"end"))

cnt=0
now=-1
maxi=0
for i in range(N+1):
    p=lists[i][0]
    if now<p:
        cnt+=1
        now=p
    elif now>p:
        maxi=max(maxi,cnt)
        cnt=1
        now=p
print(N-maxi)

Submission status: Accepted

Solution code:
#backfront
N=int(input())
lists=[]
for _ in range(N):
    x=int(input())
    lists.append((_,x))
lists.sort(key=lambda x:x[1])
lists.append((-10000000000000000,"end"))

cnt=0
now=-1
maxi=0
for i in range(N+1):
    p=lists[i][0]
    if now<p:
        cnt+=1
        now=p
    elif now>p:
        maxi=max(maxi,cnt)
        cnt=1
        now=p
print(N-maxi)

Submission status: Accepted

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

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

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

print(N-x)

Submission status: Accepted

Solution code:
N=int(input())
P=[]
for i in range(N):
    p=int(input())
    P.append(p)
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]<Q[i+1]:
        cnt+=1
    else:
        cnt=1
    ans=max(cnt,ans)

print(N-ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
index = [None]*(n+1)
for i in range(n):
    index[p[i]] = i
length = 0
now = 0
max_length = 0
for i in range(1, n+1):
    if index[i] >= now:
        now = index[i]
        length += 1
    else:
        now = index[i]
        max_length = max(max_length, length)
        length = 1
max_length = max(max_length, length)

print(n-max_length)

Submission status: Accepted

Solution code:
# AGC024B


n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = num-1

seen = [False] * n
counts =[1] * n
for num in a:
    seen[num] = True
    if num>=1 and seen[num-1]:
        counts[num] = counts[num-1] + 1
print(n - max(counts))

Submission status: Accepted

Solution code:
# AGC024B

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = num-1

seen = [False] * n
counts =[1] * n
for num in a:
    seen[num] = True
    if num>=1 and seen[num-1]:
        counts[num] = counts[num-1] + 1
print(n - max(counts))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

G = [0] * (N+1)
id = 1

for i in range(N):
    if G[P[i]-1] != 0:
        G[P[i]] = G[P[i]-1]
    else:
        G[P[i]] = id
        id+=1

C = Counter(G)

m = max(C.values())

print(N - m)

Submission status: Accepted

Solution code:
N = int(input())
dic = {}
nums = []
for i in range(N):
    num = int(input())
    dic[num] = i+1
    nums.append(num)
ans = 0
l = 0
for i in range(N-1):
    if dic[i+2] < dic[i+1]:
        ans = max(ans, l)
        l = 0
    else:
        l += 1
ans = max(ans, l)
print(N-ans-1)

Submission status: Accepted

Solution code:
n = int(input())
lis = [int(input()) for i in range(n)]
li = [-1 for i in range(n)]
for i in range(n):
    li[lis[i]-1] = i
cnt = 0
ans = n-1
for i in range(n-1):
    if li[i] < li[i+1]:
        cnt += 1
    else:
        ans = min(ans,n-1-cnt)
        cnt = 0
ans = min(ans,n-1-cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for _ in range(n)]
s = [0] * n
for i in range(n):
    s[p[i] - 1] = i
ans = 0
m = s[0]
c = 0
for i in s:
    if i >= m:
        c += 1
    else:
        ans = max(ans, c)
        c = 1
    m = i
ans = max(ans, c)
print(n - ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
p = [int(readline()) for _ in range(n)]
memo = [0] * n
for i, pp in enumerate(p):
    memo[pp - 1] = i
cnt = 1
ans = 0
for bf, af in zip(memo, memo[1:]):
    if bf < af:
        cnt += 1
    else:
        if ans < cnt:
            ans = cnt
        cnt = 1
if ans < cnt:
    ans = cnt
print(n - ans)

Submission status: Accepted

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

dp = [0 for i in range(n+1)]

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

print(n-max(dp))

Submission status: Accepted

Solution code:



"""
例２
3 2 5 1 4 6
5と6については昇順になっているので、4,3,2,1の順で配列の先頭に移動させればよい

↑のように考えると、既に並んでいる部分以外を適切な順で動かせばよいので、既に昇順のもので一番長いものをNから引くとよい？

"""

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



idxs = [None] * N
for i,p in enumerate(P):
    idxs[p-1] = i

ans = N - 1

cnt = 1

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

ans = min(ans, N - cnt)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
P = [0] * N
for i in range(N):
  P[i] = int(input())
  
# 差1で作れるもっとも長い部分列の長さをNから引く
# 例：1 3 2 4 -> 1,2もしくは3,4が最も長い
# 例：3 2 5 1 4 6 -> 3,4もしくは5,6
# 例：6 3 1 2 7 4 8 5 -> 6,7,8もしくは3,4,5もしくは1,2

seen=[0 for i in range(N+1)]
for i in range(N):
  # P[i]より1小さい数が今までに出てきていたら、その数に+1する。
  seen[P[i]] = seen[P[i] - 1] + 1
  
print(N - max(seen))

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:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n = int(input())
    idx = [-1] * n
    for i in range(n):
        p = int(input())
        p -= 1
        idx[p] = i
    
    ans = 1
    tmp = 1
    for i in range(1,n):
        if idx[i - 1] < idx[i]:
            tmp += 1
        else:
            ans = max(ans,tmp)
            tmp = 1
    ans = max(ans,tmp)
    print(n - ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import groupby

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

dic={i:0 for i in range(1,N+1)}
data=['No' for i in range(0,N)]
for i in range(0,N):
    test=P[i]
    if test!=N:
        if dic[test+1]==0:
            data[test-1]='Yes'
    dic[test]+=1

data=groupby(data)
ans=0
for key,group in data:
    g=len(list(group))
    if key=='Yes':
        ans=max(ans,g)

print(N-ans-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    p = IR(n)
    q = [None for i in range(n + 1)] + [-1]
    for i in range(n):
        q[p[i]] = i
    ans = 0
    tmp = 1
    for i in range(2, n + 2):
        if q[i - 1] < q[i]:
            continue
        ans = max(ans, i - tmp)
        tmp = i
    print(n-ans)
    return
#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
cnt=0
d=0
D=[-1]*(N+1)
for i in range(N):
  D[A[i]-1]=i
cnt=1
ans=0
for i in range(N):
  if D[i]<D[i+1]:
    cnt+=1
  else:
    ans=max(cnt,ans)
    cnt=1
print(N-ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

cnt = [0] * (N + 1)

for i in P:
    if cnt[i - 1] != 0:
        cnt[i] = cnt[i-1] + 1
        cnt[i - 1] = 0
    else:
        cnt[i] = 1

print(N - max(cnt))

Submission status: Accepted

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

dp = [0]*(n+1)

for i in range(n):
    dp[pi[i]] = dp[pi[i]-1] + 1
    
print(n-max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

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

for i in range(N):
    if P[i]==1:
        dp[i] = 1
    else:
        dp[i] = dp[idx[P[i]-1]]+1
    
print(N-max(dp))

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())
P = {int(sys.stdin.readline()): i for i in range(N)}
Q = [P[i] for i in range(1, N + 1)]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
# input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))


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

    # dp[i] = iを最後とする1づつ連続する増加列の長さ
    dp = [0]*(N+1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    """
    n = argmax(dp)とすると、
    (n - dp[n], n]は操作を行わなくてok

    逆にそれ以外の数は1回操作する
    -> N - dp[n]
    """
    N = int(input())

    dp = defaultdict(int)

    for _ in range(N):
        p = int(input())
        dp[p] = dp[p - 1] + 1
    
    print(N - max(dp.values()))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説AC
N = int(input())
MAXN = 2 * 10 ** 5

dp = [0] * (MAXN + 1)

for _ in range(N):
    p = int(input())
    dp[p] = dp[p - 1] + 1

print(N - max(dp))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# 同じ数を2回以上移動するのは無駄。最後の1回だけやればいいから。
# したがって全ての数は移動が0回または1回になる。
# 移動しない数はそのままの並び順になる。
# 逆に言えば、連続する数値からなる部分列の最長のものを見つければ、それ以外の数を移動させればよい。
# 例2では「3, 4」または「5, 6」が該当する。
# ではそれをどうやって見つけるか?
# 各数の位置を格納した配列を作る（1の位置を探して、2の位置を……とやるとO(N^2)でダメ。数列の先頭から順にやる）
# その配列を順に舐めて最大単調増加部分を見つければ良い

n = int(input())
posi = [-1] * n  # posi[i-1]には、数iの場所が0-indexで入る。

for k in range(n):
    temp = int(input())
    posi[temp - 1] = k - 1

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

maxx = max(maxx, temp)

print(n - maxx)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [-1]*(n+2)
    for i in range(1, n+1):
        x = int(input())
        a[x] = i
    x, y = 1, 1
    ans = 0
    while y < n+2:
        if a[y-1] > a[y]:
            buf = y - x
            if buf > ans:
                ans = buf
            x = y
        y += 1
    print(n - ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[int(input()) for i in range(n)]
li=[0 for i in range(n+1)]
for i,j in enumerate(l):
    li[j]=i
ans=n-1
i=1
ms=1
while i<n:
    if li[i]<li[i+1]:
        ms+=1
        i+=1
    else:
        ans=min(ans,n-ms)
        ms=1
        i+=1
print(min(ans,n-ms))

Submission status: Accepted

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

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

Submission status: Accepted

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


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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


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


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


INV = {}


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


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


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

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


if __name__ == "__main__":
    main()

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:
# coding: utf-8
# Your code here!
N=int(input())

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(N - ma)

Submission status: Accepted

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

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

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

print(N-ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline   # 439ms -> 
# input = sys.stdin.buffer.readline   # 439ms -> 188ms

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

    return N-nn

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