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:
import sys

n = int(sys.stdin.readline())
p = [None] * n
for i in range(n):
    p[i] = int(sys.stdin.readline())
a = [None] * 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)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
p = [int(sys.stdin.readline()) for i in range(n)]
a = [None] * 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)

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) 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)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# cook your dish here
n = int(input())
p = [int(input())for i in range(n)]

a = [n+1] * (n+1)
b = []
k = 1

for i in range(0,n):
    a[p[i]] = i
    
for i in range(1,n+1):
    if a[i] > a[i-1]:
        k += 1
    else:
        b.append(k)
        k = 1
    if i == n:
        b.append(k)

print(n-max(b))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    dp = [-1 for _ in range(n)]
    for _ in range(n):
        x = int(input()) - 1
        if x > 0 and dp[x - 1] != -1:
            dp[x] = dp[x - 1] + 1
        else:
            dp[x] = 1
    print(n - max(dp))

main()

Submission status: Accepted

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

straight = 1
max_straight = 1
for i in range(1, N):
    if Q[i] < Q[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1

print(N - max_straight)

Submission status: Accepted

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

link = [0] * ( n + 1)
for i in range(n):
    link[ list[i]] = link[list[i] -1] + 1
print( n - max(link))

Submission status: Accepted

Solution code:
N = int(input())
temp = [0 for x in range(N+1)]

#既に昇順に並んでいる最も長い部分列を考えて、残りの部分を動かす
#ex.[5,6,1,2,3,4]→4 [1,3,2,4]→2(12 or 34) [6,3,1,2,7,4,8,5]→3(678)

#tempに各数値を基準にした昇順の部分列をリストにし、MAX（最も長い部分列）を取る

for i in range(N):
  X=int(input())
  temp[X]=temp[X-1]+1
  
print(N-max(temp))

Submission status: Accepted

Solution code:
N = int(input())
temp = [0 for x in range(N+1)]

#+1で増加するような部分列の最長を求める

for i in range(N):
    num = int(input())
    temp[num] = 0
    temp[num] = temp[num-1]+1
    temp[num-1] = 0

print(N-max(temp))

Submission status: Accepted

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

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy
# sys.setrecursionlimit(1000000)

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(input())
    an = [int(input()) for i in range(n)]
    assert len(an) == n
    sublen = [0 for i in range(n + 1)]
    for i in range(n):
        a1 = an[i]
        sublen[a1] = sublen[a1 - 1] + 1
    res = max(sublen)
    print(n - res)

main()

Submission status: Accepted

Solution code:
import sys
from sys import stdin, stdout

rem=10**9+7
sys.setrecursionlimit(10 ** 6)
take = lambda: map(int, stdin.readline().split())

n=input()
ans=[1 for i in range(n+1)]
pos={}
for i in range(1,n+1):
    x=take()[0]
    pos[x]=i
for i in range(n-1,0,-1):
    if pos[i]<pos[i+1]:
        ans[i]=ans[i+1]+1
#print(ans)
print n-max(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
d = {}
for i in range(len(a)):
    if a[i] - 1 in d:
        v = d[a[i] - 1]
        del d[a[i] - 1]
        d[a[i]] = v + 1
    else:
        d[a[i]] = 1
print(len(a) - max(list(d.values())))

Submission status: Accepted

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

indeces = [0] * n

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

ans = 0
pre_ans = 0

for i in range(n - 1):
	if indeces[i] < indeces[i + 1]:
		pre_ans += 1
	else:
		if pre_ans > ans:
			ans = pre_ans
		pre_ans = 0

if pre_ans > ans:
	ans = pre_ans

print(n - ans - 1)

Submission status: Accepted

Solution code:
import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


N = ii()
P = []
for _ in range(N):
    p = ii()
    P.append(p-1)

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

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

    maxcnt = max(maxcnt, cnt)

print(N - maxcnt)

Submission status: Accepted

Solution code:
n = int(input())
t = [0]*n
for i in range(n):
    p = int(input())-1
    t[p] = i
maxi = 1
c = 1
for i in range(n-1):
  a = t[i]
  b = t[1+i]
  if a < b:
    c += 1
  else:
    maxi = max(c,maxi)
    c = 1
maxi = max(c,maxi)
print(n - maxi)

Submission status: Accepted

Solution code:
n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=0
num=0
n_th = 0
s={}
for i in p:
	if i-1 in s:
		s[i]=s[i-1]+1
	else:
		s[i]=1
print(n-max(s.values()))

Submission status: Accepted

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

s = {}
for i in l:
    if i - 1 in s:
        s[i] = s[i - 1] + 1
        del s[i - 1]
    else:
            s[i] = 1
print(n - max(s.values()))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    l = [ int(input().rstrip()) for i in range(n)]

    s = {}
    for i in l:
        if i - 1 in s:
            s[i] = s[i - 1] + 1
            del s[i - 1]
        else:
            s[i] = 1
    print(n - max(s.values()))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
P = []
for i in xrange(N):
	P.append(input())
Q = {}
for i in xrange(N):
	Q[P[i]-1]=i
longest_length = 0
length_of_sequence = 1
for i in xrange(N-1):
	if Q[i+1] > Q[i]:
		length_of_sequence += 1
	else:
		longest_length = max(longest_length, length_of_sequence)
		length_of_sequence = 1
longest_length = max(longest_length, length_of_sequence)
print N - longest_length

Submission status: Accepted

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

Q = range(N)

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

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

print N-max-1

Submission status: Accepted

Solution code:
import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


N = ii()
P = []
for _ in range(N):
    p = ii()
    P.append(p-1)

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

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

    maxcnt = max(maxcnt, cnt)

print(N - maxcnt)

Submission status: Accepted

Solution code:
N = int(input())
dp = [None for _ in range(N)]
for i in range(N):
  p = int(input())
  if dp[p - 2] == None or p == 1:
    dp[p - 1] = 1
  else:
    dp[p - 1] = dp[p - 2] + 1
print(N - max(dp))

Submission status: Accepted

Solution code:
N = int(input())
a = [0]
for _ in range(N):
  a.append(int(input()))

Q = [0 for i in range(N + 1)]
for i in range(N + 1):
    Q[a[i]] = i
ans = 1
num = 1

for idx in range(2, len(Q)):
    if Q[idx - 1] < Q[idx]:
        num += 1
    else:
        ans, num = max(num, ans), 1

print(N - max(num, ans))

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
x,r,num,ans = [0 for i in range(n)],0,1,0
for i in range(n): x[p[i]-1] = i
while r!=n-1:
	r += 1
	if x[r-1]<x[r]: num = num+1
	else: ans,num = max(ans,num),1
ans = max(ans,num)
print(n-ans)

Submission status: Accepted

Solution code:
#agc024b

n=int(raw_input())
p=[]
for i in xrange(n):
 p.append(int(raw_input()))
r=[0]*(n+1)
for x in p:
 r[x]=r[x-1]+1
print n-max(r)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N=int(input())
P=[int(input())-1 for i in range(N)]
Q=[0 for i in range(N)]
for i in range(N):
    Q[P[i]]=i
L=[1]
k=0
for i in range(1,N):
    if Q[i-1]<Q[i]:
        L[k]+=1
    else:
        L.append(0)
        k+=1
        L[k]+=1
print(N-max(L))

Submission status: Accepted

Solution code:

class Backfront:
    max_to_min = {}

    def add(self, x):
        if x - 1 in self.max_to_min:
            self.max_to_min[x] = self.max_to_min[x - 1]
            del self.max_to_min[x - 1]
        else:
            self.max_to_min[x] = x

    def longest_seq(self):
        return 1 + max([y - x for (y, x) in self.max_to_min.items()])

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

    backfront = Backfront()
    for _ in range(n):
        x = int(input())
        backfront.add(x)

    print("{0:d}".format(n - backfront.longest_seq()))

main()

Submission status: Accepted

Solution code:
n = int(input())

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


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

result = 1
temp = 1
for i in range(1, n):
    if q[i] < q[i-1]:
        if temp > result:
            result = temp
        temp = 1
    else:
        temp += 1

if temp == n:
    result = temp

print(n - result)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    d = {}
    d[0] = -1
    for i in range(n):
        d[I()] = i
    r = n - 1
    c = 0
    for i in range(1,n+1):
        if d[i-1] > d[i]:
            if r > n - c:
                r = n - c
            c = 1
        else:
            c += 1
    if r > n - c:
        r = n - c

    return r




print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Grand Contest 024 B問題 WA
Author     : Kitaura Hiromi
LastUpdate : 20180520
Since      : 20180520
"""
N = int(input())
p = [int(input()) for i in range(N)]
q = [0 for i in range(N)]
for i in range(N):
    q[p[i]-1] = i

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

Submission status: Accepted

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
Q = [0 for i in range(N+1)]
res = 100000000000000
for i in range(N):
	Q[P[i]] = Q[P[i] - 1] + 1
	res = min(res, N-Q[P[i]])
	
print(res)

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

cnt=0
tmp=0
for i in range(N-1):
    if Q[i]<Q[i+1]:
        cnt+=1
    else:
        if tmp<cnt+1:
            tmp=cnt+1
        cnt=0

if tmp==0:
    tmp=cnt+1

print(N-tmp)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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


# 連続している最大値を求める

lengths = {}
for pn in p:
    if pn in lengths:
        lengths[pn+1] = lengths[pn] + 1
    else:
        lengths[pn+1] = 1
    
max_count = max(lengths.values())
print(n-max_count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 20 20:55:50 2018
AGC024B
@author: maezawa
"""

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

max_cnt = 0
cnt = 1
qpre = q[0]
 
for i in range(1,n):
    if q[i] > qpre:
        cnt += 1
    else:
        if max_cnt < cnt:
            max_cnt = cnt
        cnt = 1
    qpre = q[i]
if max_cnt < cnt:
    max_cnt = cnt

print(n-max_cnt)

Submission status: Accepted

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

d = [0]*(N+1)
for p in P:
    d[p] = d[p-1]+1

print(N-max(d))

Submission status: Accepted

Solution code:
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


@mt
def slv(N, P):
    Q = [-1] * N
    for i, p in enumerate(P):
        Q[p - 1] = i

    p = -1
    mc = 0
    c = 0
    for q in Q:
        if q > p:
            c += 1
        else:
            c = 1
        mc = max(mc, c)
        p = q

    return N - mc


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

    print(slv(N, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

print(N - max(LCIS))

Submission status: Accepted

Solution code:
N = int(input())
n_list_idx = [0 for _ in range(N + 1)]
for i in range(N):
    v = int(input())
    n_list_idx[v] = i

o_max = 1
o = 1
for i in range(2, len(n_list_idx)):
    if n_list_idx[i] > n_list_idx[i - 1]:
        o += 1
    else:
        if o > o_max:
            o_max = o
        o = 1
if o > o_max:
    o_max = o
print(N - o_max)

Submission status: Accepted

Solution code:

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

    num = [[j, i] for i, j in enumerate(P)]
    num.sort()
    cnt, maxcnt = 1, 1
    for i in range(N - 1):
        if num[i][1] < num[i+1][1]:
            cnt += 1
            maxcnt = max(maxcnt, cnt)
        else:
            cnt = 1
    print(N - maxcnt)

main()

Submission status: Accepted

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

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

print(N-M)

Submission status: Accepted

Solution code:

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

    num = []
    apnd = num.append
    for i, j in enumerate(P):
        apnd([j, i])
    num.sort()

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

main()

Submission status: Accepted

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

q_dict = {0:0}
for i in range(n):
    q_dict[p_list[i]] = i
length = 0
ans = 1
for i in range(1, n+1):
    if q_dict[i] > q_dict[i-1]:
        length += 1
        if length > ans:
            ans = length
    else:
        length = 1
print(n - ans)

Submission status: Accepted

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

    #f1(N, P)
    editorial(N, P)


def editorial(N, P):
    """
    入力例3
        N=8
        P=63127485
         |6   7 8 |
         | 3   4 5|
         |  12    |
        上記の3つの列は要素ai+1=aiである部分列
            連続する列が長いほど、移動しなくて済む要素は多い
            連続するためには、最小未満は左・最大より大きいものは末尾に移動する
        部分列(wikipediaより)
            残った要素がもとの数列における相対的な序列を保つ
            与えられた列からいくつかの要素を取り去ることによって得られる列
    ksomemo様にお借りしました
    """
    if N == 1:
        print(0)
        return

    # WA(N, P)
    a = [0] * (N+1)
    for i, p in enumerate(P):
        a[p] = i

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


def WA(N, P):
    tmp = 0
    ans = 0
    for i, p in enumerate(P):
        if i == 0 or P[i-1] + 1 == p:
            tmp += 1
        else:
            ans = max(ans, tmp)
            tmp = 1

    print(N - ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    #f1(N, P)
    editorial(N, P)


def editorial(N, P):
    """
    入力例3
        N=8
        P=63127485
         |6   7 8 |
         | 3   4 5|
         |  12    |
        上記の3つの列は要素ai+1=aiである部分列
            連続する列が長いほど、移動しなくて済む要素は多い
            連続するためには、最小未満は左・最大より大きいものは末尾に移動する
        部分列(wikipediaより)
            残った要素がもとの数列における相対的な序列を保つ
            与えられた列からいくつかの要素を取り去ることによって得られる列
    """
    if N == 1:
        print(0)
        return

    # WA(N, P)
    a = [0] * (N+1)
    for i, p in enumerate(P):
        a[p] = i

    tmp = 1
    max_len = 1
    for i in range(1, N):
        if a[i] < a[i+1]:
            tmp += 1
            max_len = max(max_len, tmp)
        else:
            tmp = 1

    ans = N - max_len
    print(ans)


def WA(N, P):
    tmp = 0
    ans = 0
    for i, p in enumerate(P):
        if i == 0 or P[i-1] + 1 == p:
            tmp += 1
        else:
            ans = max(ans, tmp)
            tmp = 1

    print(N - ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
P=[None]*(N+1)
for i in range(1,N+1):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

Q=[0]*(N+2)

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

count=0
Ans=0
for i in range(1,N+2):
    if Q[i]>Q[i-1]:
        count+=1
    else:
        Ans=max(count,Ans)
        count=1

print(N-Ans)

Submission status: Accepted

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

subset_num = num = 0
for i in range(N-1):
    num += 1
    if Q[i] > Q[i+1]:
        subset_num = max(subset_num, num)
        num = 0
else:
    num += 1   # 最後だけ数えられないので注意
    subset_num = max(subset_num, num)
print(N - subset_num)

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

count = 0
check = 0
maxlen = 0
for i in Q:
    if check < i:
        count += 1
        check = i
    else:
        maxlen = max(count, maxlen)
        count = 1
        check = i
maxlen = max(count, maxlen)
print(N-maxlen)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
p=[]
q=[0 for i in range(n)]
for i in range(n):   
 p.append(i1())
 q[p[-1]-1]=i
k=1
s=0
for i in range(n-1):
  if q[i+1]-q[i]>0:
     k+=1
  else:
     s=max(s,k)
     k=1
s=max(s,k)
print(n-s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ppp = list(map(int, (input() for _ in range(n))))

tmp = [0] * (n + 1)
for p in ppp:
    tmp[p] = tmp[p - 1] + 1

print(n - max(tmp))

Submission status: Accepted

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

import math
import sys
import itertools
import numpy as np

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

a = [0]*(n)
for i in range(n):
    a[t[i]-1]=i
lmax =1
length=1

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

print(n - lmax)

Submission status: Accepted

Solution code:
N = int(input())

Qs = [0 for _ in range(N)]
for i in range(N):
    tmp = int(input())
    Qs[tmp - 1] = i - 1

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

print(N - max(result, tmp))

Submission status: Accepted

Solution code:
N = int(input())
a = [0]*N
cnt = 0
dic = {}
for i in range(N):
	a[i] = int(input())
	dic[a[i]] = i

ans = 1
cnt = 1
for num in range(1,N):
	if dic[num] < dic[num+1]:
		cnt += 1
	else:
		ans = max(cnt,ans)
		cnt = 1


ans = max(cnt,ans)
print(N-ans)

Submission status: Accepted

Solution code:
n=int(input())
p=[int(input())-1for _ in[0]*n]
q=[0]*n
for i in range(n):q[p[i]]=i
r,c=0,1
for i in range(n-1):
    c=c+1if q[i]<q[i+1]else 1
    if r<c:r=c
if r<c:r=c
print(n-r)

Submission status: Accepted

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

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

"""
for i in reversed(range(n)):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1

        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
"""
for i in range(n):
    visited[p[i]] = visited[p[i] - 1] + 1
print(n - max(visited))

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
tl = 1
n2i = [-1 for i in range(n)]
for i in range(n):
    n2i[p[i]-1] = i
tmp = 1
for i in range(n-1):
    if n2i[i] < n2i[i+1]:
        tmp += 1
    else:
        tmp = 1
    tl = max(tl, tmp)

ans = n - tl
print(ans)

Submission status: Accepted

Solution code:
import sys
if __name__ == "__main__":
    N = int(input())
    P = []
    Q = [0]*(N+1)
    for i in range(1, N+1):
        p = int(input())
        Q[p] = i

    # 1 4 5 2 3 -> 4 5を移動
    # 1 4 5 3 2 -> 3 4 5 を移動
    # 5 2 1 3 4 -> 1 5 を移動
    cur = 1
    max_cur = 1
    for i in range(1, N):
        if Q[i] < Q[i+1]:
            cur += 1
            max_cur = max(cur, max_cur)
        else:
            cur = 1
    print(N - max_cur)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
 
al= {}
ans=0
for ai in a:
  if ai - 1 in al.keys():
    al[ai]=al[ai-1]+1
    ans=max(ans,al[ai-1]+1)   
    del al[ai-1]
  else:
    al[ai]=0

print(n-ans-1)

Submission status: Accepted

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

check = [0] * N

for i in P:
    if check[i-1] == 0:
        if (i-2 >= 0 and check[i-2] == 0) or i == 1:
            check[i-1] = 1
        else:
            check[i-1] = 2
count = 0
ans = 0
for i in range(N):
    if check[i] == 2:
        count += 1
    else:
        ans = max(ans, count)
        count = 1
ans = max(ans, count)

print(N-ans)

Submission status: Accepted

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

al= {}
ans=0
for ai in a:
  if ai - 1 in al.keys():
    al[ai]=al[ai-1]+1
    ans=max(ans,al[ai-1]+1)   
    del al[ai-1]
  else:
    al[ai]=0
    if ai + 1 in al.keys():
      del al[ai]
print(n-ans-1)

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(input()) for _ in range(n)]
mem = [0] * (n + 1)
a, b = 1, 1
s = 0
for i in range(n):
    mem[nums[i]] += i

p, q = mem[1], mem[n]

for i in range(2, n+1):
    if  p < mem[i]:
        a += 1
    else:
        s = max(s, a)
        a = 1
    p = mem[i]
s = max(s, a)
for j in range(n, 0, -1):
    if  q > mem[j]:
        b += 1
    else:
        s = max(s, b)
        b = 1
    q = mem[j]
s = max(s, b)
print(n - s)

Submission status: Accepted

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


P = [0] * (N + 1)

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


print(N-max(P))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
  x=int(input())
  a.append(x)
d={}
f=0
maxi=0
for i in range(n):
  if((a[i]-1) in d):
    d[a[i]]=d[a[i]-1]+1
  else:
    d[a[i]]=1

for i in d:
  if(i==0):
    maxi=d[i]
  else:
    if(d[i]>maxi):
      maxi=d[i]

print(n-maxi)

Submission status: Accepted

Solution code:
N = int(raw_input())
P = []
p_hash = {}
for i in range(N):
    num = int(raw_input())
    P.append(num)
    p_hash[num] = i

now_pos = p_hash[1]
count_1 = 1
max_1 = 1
for i in range(1,N):
    pos_new = p_hash[i+1]
    if pos_new > now_pos:
        count_1 += 1
        max_1 = max(max_1,count_1)
        now_pos = pos_new
    else:
        max_1 = max(max_1,count_1)
        count_1 = 1
        now_pos = pos_new

print(N - max_1)

Submission status: Accepted

Solution code:
n = int(input())
lens = [False for i in range(n + 1)]

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

ps = []
for i in range(n + 1):
    if lens[i]:
        ps.append(i)

ps.sort()
x = 0
temp = 0
for i in ps:
    x = max(i - temp, x)
    temp = i
print(n - x)

Submission status: Accepted

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

ans=0
count=0
bef=0
for i,j in a:
    if j>bef:
        count+=1
        ans=max(ans,count)
    else:
        count=1
    bef=j
print(n-ans)

Submission status: Accepted

Solution code:
N = int(input())

l = list(range(N))

for n in range(N):
    l[n] = int(input())

# print(l)

count_l = []
ind_list = [0] * N

for i, k in enumerate(l):
    ind_list[k-1] = i

count = 1
for i in range(N):
    if i == N - 1:
        count_l.append(count)
    else:
        if ind_list[i] < ind_list[i+1]:
            count += 1
        else:
            count_l.append(count)
            count = 1

print(N - max(count_l))

Submission status: Accepted

Solution code:
N = int(input())
a = [int(input()) for i in range(N)]
b = [0]*N
for i in range(N):
    b[a[i] - 1] = i
b.append(-1)
count = 1
max = 0
for i in range(N):
    if b[i+1] - b[i] > 0:
        count = count + 1
    else:
        if count > max:
            max = count
        count = 1

print(N - max)

Submission status: Accepted

Solution code:
N = int(input())

Ps = [(int(input()), i) for i in range(N)]
Ps.sort()

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

Submission status: Accepted

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

    idx = make_index(p)
    c = count_sequence(p, idx)
    ans = n - c
    print(ans)

def make_index(p):
    idx = dict()
    for i, v in enumerate(p):
        idx[v] = i
    return idx

def count_sequence(p, idx):
    cmax = 0
    c = 0
    i = -1

    x = 1
    while True:
        j = idx.get(x, None)
        if j is None:
            cmax = max(cmax, c)
            break
        elif j < i:
            cmax = max(cmax, c)
            c = 1
            i = j
        else:
            c += 1
            i = j
        x += 1

    return cmax

main()

Submission status: Accepted

Solution code:
import sys,collections,random,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
d = collections.defaultdict(int)
for i in range(n):
    d[I()] = i
d[0] = n
t,maxinc = 0,0
for i in range(1,n+1):
    if d[i-1] < d[i]:
        t += 1
        maxinc = max(maxinc,t)
    else:
        t = 0
print(n-1-maxinc)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
def inpl(): return map(int, input().split())

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

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

print(N - max(score))