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:
#!/usr/bin/env python3
#AGC24 B

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AGC024B - Backfront
def main():
    N, *P = map(int, open(0).read().split())
    # dp[i] := length of a monotonically increasing subsequence which i comes at the end
    dp = [0] * (N + 1)
    for i in P:
        dp[i] = dp[i - 1] + 1
    ans = N - max(dp)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(N - ma)

Submission status: Accepted

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

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

print(N - max(dp))

Submission status: Accepted

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

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

print(n-res)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 「移動されるものとされないもの」という区分け
# 最も長く数字が並ぶものを探すというのはできていたんだけどな...
N = int(input())
P = [int(input()) for i in range(N)]

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

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

print(N - k)

Submission status: Accepted

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

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

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

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

    print(N - length)

sol()

Submission status: Accepted

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

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

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

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

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

    print(N - maxLeng)

sol()

Submission status: Accepted

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

# 抜き取るだけ抜き取ってから、自由に追加していくと思える
# 残す部分が「完成」している必要がある
# L,L+1,...,Rの左右が出来ているようなものを残せる

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

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

max_rest = 1
# 各数字が右端に来るときの最大長を持つ
x = 1
for n in range(2,N+1):
    if p_to_i[n] > p_to_i[n-1]:
        x += 1
        if max_rest < x:
            max_rest = x
    else:
        x = 1

answer = N - max_rest
print(answer)

Submission status: Accepted

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

import numpy as np

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

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

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

# dp[i]: i より前に何個連続してるか
dp = np.zeros(N + 1, dtype=int)
for i in range(N):
    p = P[i]
    dp[p] = dp[p - 1] + 1
print(N - dp.max())

Submission status: Accepted

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

Submission status: Accepted

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

N = int(input())

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

T = [0]*(N-1)

E = [0]*N

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

max_score = 0
prev = -1

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

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

print(N-max_score)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

dp = [0]*(N+1)

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

ans = N - max(dp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce

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

INF = 10**15

# Pの逆写像
Q = {p: i for i, p in enumerate(P, 1)}

# j以上の整数を末尾に移動する場合に、先頭に移動すべき整数の個数を求める
ans, _ = reduce(
    lambda acc, j: (
        min(
            acc[0],
            acc[1] + N - j + 1
        ),
        acc[1] if j > N or Q[j - 1] < Q[j] else
        j - 1
    ),
    range(2, N + 2),
    (INF, 0)
)

# 出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

longest_increasing_subsequence = [0]*(N+1) #[i]: i以下の数字による最長増加部分文字列

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

#print(longest_increasing_subsequence)
print(N - max(longest_increasing_subsequence))

Submission status: Accepted

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

Submission status: Accepted

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

n = i()
p = hip(n)

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

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

print(n - ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

N=int(input())

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(N + min(T))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


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

    # dp[i]: 末尾がiになる正しい順序に並んでいる部分列の長さ
    dp = [0] * (n + 1)
    for p in P:
        dp[p] += dp[p - 1] + 1

    return n - max(dp)


print(main())

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


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

    # dp[i]: 末尾がiになる正しい順序に並んでいる部分列の長さ
    dp = [0] * (n + 1)
    for i in range(n):
        dp[P[i]] += dp[P[i] - 1] + 1

    return n - max(dp)


print(main())

Submission status: Accepted

Solution code:
from functools import reduce

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

INF = 10**15

# Pの逆写像
Q = {p: i for i, p in enumerate(P, 1)}

# j以上の整数を末尾に移動する場合に、先頭に移動すべき整数の個数を求める
ans = reduce(
    lambda acc, j: (
        min(
            acc[0],
            acc[1] + N - j + 1
        ),
        acc[1] if j > N or Q[j - 1] < Q[j] else
        j - 1
    ),
    range(2, N + 2),
    (INF, 0)
)[0]

# 出力
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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

INF = 10**15

# Pの逆写像
Q = {p: i for i, p in enumerate(P, 1)}

# j以上の整数を末尾に移動する場合に、先頭に移動すべき整数の個数を求める
ans = reduce(
    lambda acc, j: (
        min(
            acc[0],
            acc[1] + N - j + 1
        ),
        acc[1] if j > N or Q[j - 1] < Q[j] else
        j - 1
    ),
    range(2, N + 2),
    (INF, 0)
)[0] if N >= 2 else 0

# 出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# This Python 3 environment comes with many helpful analytics libraries installed
# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python
# For example, here's several helpful packages to load in 

import numpy as np # linear algebra
#import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)

# Input data files are available in the "../input/" directory.
# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory

import os
#print(os.listdir("../input"))

import sys
#def input():
#    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
'''
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
'''

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

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

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

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

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:
import sys
input = sys.stdin.readline

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

Submission status: Accepted

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

p = [0] * n

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

Submission status: Accepted

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


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

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

print(N - max(dp))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(N - max(Chain))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

counter = [0] * (N + 1)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

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


N = d_in()

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

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

print(N - ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

print(int(x) - result)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

stay_num_cnt = 0
cnt = 0
t = 0
for x in q:
    if x >= t:# x == tはあり得ない
        cnt += 1
    else:
        cnt = 1
    t = x
    stay_num_cnt = max(stay_num_cnt, cnt)
print(n - stay_num_cnt)#, q)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

n = ni()
p = []

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

dp = [0]*(n+1)

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

print(n - max(dp))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

from math import *

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

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

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

    print N - max_count


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
p = [int(sys.stdin.readline()) for i in range(n)]
a = [0] * n
for i in range(n):
    a[p[i]-1] = i
prv = -1
mx = 1
nw = 0
for i in range(n):
    if prv < a[i]:
        nw += 1
        mx = max(mx, nw)
    else:
        nw = 1
    prv = a[i]
print(n-mx)