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: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())

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


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

print(N-max_con)

Submission status: Wrong Answer

Solution code:
N=int(input())

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


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

print(N-max_con)

Submission status: Wrong Answer

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

mm1 = N
cnt1 = 0
for i in range(N-1,-1,-1):
    if P[i]==mm1:
        mm1 -= 1
        cnt1 += 1

mm2 = 0
cnt2 = 0
for i in range(N):
    if P[i]==mm2:
        mm2 += 1
        cnt2 += 1

print(N-max(cnt1,cnt2))

Submission status: Wrong Answer

Solution code:
N = int(input())

P = []
s = 0
for _ in range(N):
  p = int(input())
  P.append(p)
  if p == s+1:
    s += 1

t = N+1
for p in reversed(P):
  if p == t-1:
    t -= 1

print(min(t-1, N-s))

Submission status: Wrong Answer

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

import sys

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

N = INT()
A = LIST(N)

cnt1 = 0
nxt = 1
for a in A:
    if a == nxt:
        cnt1 += 1
        nxt += 1

cnt2 = 0
nxt = N
for a in A[::-1]:
    if a == nxt:
        cnt2 += 1
        nxt -= 1

ans = N - max(cnt1, cnt2)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
cnt1 = 1
cnt2 = n
for i in range(n):
  if a[i] == cnt1:
    cnt1 += 1
  if a[-i-1] == cnt2:
    cnt2 -= 1
print(n-max(cnt1-1,n-cnt2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
cnt1 = 1
cnt2 = n
for i in range(n):
  if a[i] == cnt1:
    cnt1 += 1
  if a[-i-1] == cnt2:
    cnt2 -= 1
print(n-max(cnt1,n-cnt2))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ascend = 0
for i in range(N):
    if P[i] == ascend+1:
        ascend += 1

descend = 0
for i in reversed(range(N)):
    if P[i] == N-descend:
        descend += 1

print(min(N-ascend,N-descend))

Submission status: Wrong Answer

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

cnt1 = 0
search = 1
for p in P:
  if p == search:
    cnt1 += 1
    search += 1

cnt2 = 0
search = N
P = P[::-1]
for p in P:
  if p == search:
    cnt2 += 1
    search -= 1
    
print(N - max(cnt1, cnt2))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
count = 1
flag = ""
for i in range(1,N):
    if flag == "":
        if P[i-1] < P[i]:
            flag = "<"
        else:
            flag = ">"
    else:
        if (P[i-1] < P[i] and flag == "<") or (P[i-1] > P[i] and flag == ">"):
            continue
        else:
            count += 1
            if P[i-1] < P[i]:
                flag = "<"
            else:
                flag = ">"
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
count = 0
if P[0] != 1:
    count += 1
for i in range(1,N):
    now = P[i]
    if now == i+1:
        continue
    else:
        if P[i-1] + 1 == now:
            continue
        else:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
m, k = 0, 0
for i in range(N):
  if A[i] == m + 1:
    m += 1
  if A[N - 1 - i] == N - k:
    k += 1
print(N - max(m, k))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def examB():
    N = I(); P = [I() for _ in range(N)]
    cur = 0; ansC = N
    for i in range(N):
        if P[i]==cur:
            ansC -=1
            cur  +=1
    ans = ansC
    cur = N; ansC = N
    for i in range(N-1,-1,-1):
        if P[i]==cur:
            ansC -=1
            cur  -=1
    ans = min(ans,ansC)
    print(ans)

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

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

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

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

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

print(N - res)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ret = 0
cur = N
for p in P[::-1] :
    if p == cur :
        cur -= 1
        ret += 1
        
print(N - ret)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
index=1
count1=0
for i in range(n):
  if l[i]==index:
    count1+=1
    index+=1
index=n
count2=0
for i in range(1,n+1):
  if l[-i]==index:
    count2+=1
    index-=1
num=max(count1,count2)
print(n-num)

Submission status: Wrong Answer

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

ans=0
t=1
tmp=0
for x in A:
  if t==x:
    t+=1
    tmp+=1
ans=N-tmp
t=N
tmp=0
for x in reversed(A):
  if t==x:
    t-=1
    tmp+=1
ans=min(ans,N-tmp)
print(ans)

Submission status: Wrong Answer

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

ans=0
t=1
tmp=0
for x in A:
  if t==x:
    t+=1
    tmp+=1
ans=N-tmp
t=N
tmp=0
for x in reversed(A):
  if t==x:
    t-=1
    tmp+=1
ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
li = [int(input()) for _ in range(N)]
num = N
cnt = 0
for i in li[::-1]:
  if i == num:
    cnt += 1
    num -= 1
print(N - cnt)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
p=[int(input()) for _ in range(n)]
m=p[0]
ans=0
for i in range(n):
    if p[i]<m:
        ans=max(ans,p[i])
    else:
        m=p[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
p=[int(input()) for _ in range(n)]
ans=0
for i in range(n-1,-1,-1):
    if p[i]!=i+1:
        ans=p[i]
        break
print(ans)

Submission status: Wrong Answer

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

tmp1 = n
ans1 = n
p = p[::-1]
for i in range(n):
    if p[i] == tmp1:
        ans1 -= 1
        tmp1 -= 1
    #print(p[i], tmp1, ans1)

tmp2 = 1
ans2 = n
p = p[::-1]
for i in range(n):
    if p[i] == tmp2:
        ans2 -= 1
        tmp2 += 1
    #print(p[i], tmp1, ans1)

print(min(ans1, ans2))

Submission status: Wrong Answer

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

tmp1 = n
ans1 = n
p = p[::-1]
for i in range(n):
    if p[i] == tmp1:
        ans1 -= 1
        tmp1 -= 1
    #print(p[i], tmp1, ans1)

tmp2 = 1
ans2 = 0
p = p[::-1]
for i in range(n):
    if p[i] == tmp2:
        ans2 += 1
        tmp2 += 1
    #print(p[i], tmp1, ans1)

print(max(ans1, ans2))

Submission status: Wrong Answer

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

tmp = n
ans = n
p = p[::-1]
for i in range(n):
    if p[i] == tmp:
        ans -= 1
        tmp -= 1
    #print(p[i], tmp, ans)

print(ans)

Submission status: Wrong Answer

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

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

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

print(n - ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

front = 0
for i in range(n):
  if front + 1 == a[i]:
    front += 1

back = n+1
for i in range(n-1,-1,-1):
  if back - 1 == a[i]:
    back -= 1

print(min(back-1, n-front))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
n = int(input())
p = [int(input()) for i in range(n)]
a = 1
for i in p:
    if i == a:
        a += 1
b = 1
for i in p[::-1]:
    if i == n-b+1:
        b += 1
print(n-max(a,b)+1)

Submission status: Wrong Answer

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

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

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

print (N - count)
# print (lst)

Submission status: Wrong Answer

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

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

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

print (N - count)
# print (lst)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

check = [0] * N
count = 0
for i in range(N):
    if check[i] != 0:
        continue
    j = i + 1
    start = P[i]
    tmp = 1
    while j < N:
        if P[j] == start + tmp:
            check[j] += 1
            tmp += 1
            j += 1
        elif P[j] < start + tmp:
            j += 1
        else:
            break
    count = max(count, tmp)

print (N - count)

Submission status: Wrong Answer

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


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

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

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

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

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

    len_max = 1
    count = 1

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

    print(n - len_max)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

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

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

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

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

    len_max = 0
    count = 1

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

    print(n - len_max)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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

    # 昇順に並んでいるかどうか
    # 先頭と末尾のどちらにも移動しうる場合が存在する可能性を否定できない

    # 先頭からチェック
    min_n = 1
    candidate1 = 0

    for i in range(n):
        if p[i] == min_n:
            min_n += 1
        else:
            candidate1 += 1

    # 末尾からチェック
    max_n = n
    candidate2 = 0

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

    print(min(candidate1, candidate2))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

    print(N - max(dp))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    dp = [0] * N

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    dp = [0] * N

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [0]*(n+1)

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

succ = [1] * (n+1)

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

print(n-max(succ))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
p = [int(input()) for _ in range(N)]
q = [0] * (N + 1)
for i in range(N):
  q[p[i]] = i
res = 0
temp = 0
for i in range(2, N + 1):
  if q[i - 1]  < q[i]:
    temp += 1
  else:
    res = max(res, temp)
    temp = 0

print(N - res - 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
N = int(input())
p = [int(input()) for _ in range(N)]
inf = 10 ** 6
lis = [inf] * N
res = 0
for i in range(N):
  ind = bl(lis, p[i])
  lis[ind] = p[i]
  res = max(res, ind)
print(N - res)

Submission status: Wrong Answer

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

a1 = 0
s1 = 1
for i in range(N):
  if P[i] == s1:
    a1 += 1
    s1 += 1
a2 = 0
s2 = N
for i in range(N-1,-1,-1):
  if P[i] == s2:
    a2 += 1
    s2 -= 1
print(min(N-a1,N-a2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ls = [0]*(N+1)
for i in range(N):
  p = int(input())
  ls[p] = i
ID = -1
count = 0
ans = 0
for a in range(1,N):
  if ls[a+1]>ls[a]:
    count += 1
  else:
    if count>ans:
      ans = count
    count = 0
print(N-ans-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ls = [0]*(N+1)
for i in range(N):
  p = int(input())
  ls[p] = i
count = 0
for a in range(N,0,-1):
  if ls[a]>ls[a-1]:
    count += 1
  else:
    break
print(N-count-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=[int(input()) for i in range(n)]
ct=1
for i in range(n):
  if p[i]==ct:
    ct+=1
ct2=n
for i in range(n-1,-1,-1):
  if p[i]==ct2:
    ct2-=1
print(n-max(ct-1,n-ct2))

Submission status: Wrong Answer

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

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

# 動かす必要のない部分の最大の長さ
max_length = 0

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

print(N - max_length)

Submission status: Wrong Answer

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

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

# 動かす必要のない部分の最大の長さ
max_length = 0

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

print(N - max_length)

Submission status: Wrong Answer

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

idxs = {}
for i in range(N):
    idxs[P[i]] = i

# 動かす必要のない部分の最大の長さ
max_length = 0

cnt = 1
for i in range(1, N):
    if idxs[i] < idxs[i+1]:
        cnt += 1
        max_length = max(max_length, cnt)
    else:
        cnt = 1



print(N - max_length)

Submission status: Wrong Answer

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

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

# 動かす必要のない部分の最大の長さ
max_length = 0

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

print(N - max_length)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = [0 for _ in range(N)]
    for i in range(N):
        ind[A[i]-1] = i
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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)]
dp = [inf]*n
for i in range(n):
    r = br(dp,p[i])
    dp[r] = p[i]
print(dp.count(inf) + 1)

Submission status: Wrong Answer

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)]
que = deque(p)
ans = 0
tmp = 0
while que:
    x = que[tmp]
    if x == que[-1] + 1:
        que.remove(x)
        que.append(x)
        ans += 1
    elif x + 1 == que[0]:
        que.remove(x)
        que.appendleft(x)
        ans += 1
    else:
        tmp += 1
    if tmp == n:
        break
for i in range(n):
    if que[i] -1 != i:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
if n==1:print(0);sys.exit()
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)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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:
        incmax = max(incmax, inc)
        inc = 1
    before = vi[v]
print(N - incmax)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
vi = {v: i for i, v in enumerate(P)}
before = float('inf')
for v in range(N, -1, -1):
    if v == 0 or vi[v] > before:
        break
    else:
        before = vi[v]
before = -1
for v2 in range(1, N + 2):
    if v2 == N + 1 or vi[v2] < before:
        break
    else:
        before = vi[v2]
print(min(v, N - v2))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
vi = {v: i for i, v in enumerate(P)}
before = float('inf')
for v in range(N, -1, -1):
    if v == 0 or vi[v] > before:
        break
    else:
        before = vi[v]
before = -1
for v2 in range(1, N + 2):
    if v2 == N + 1 or vi[v2] < before:
        break
    else:
        before = vi[v2]
print(min(v, v2))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
vi = {v: i for i, v in enumerate(P)}
before = float('inf')
for v in range(N, -1, -1):
    if v == 0 or vi[v] > before:
        break
    else:
        before = vi[v]
print(v)

Submission status: Wrong Answer

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 = 0
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: Wrong Answer

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