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:
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 - ans)

Submission status: Wrong Answer

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

print(N - ans)

Submission status: Wrong Answer

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]
print(n - ans)

Submission status: Wrong Answer

Solution code:
# 「移動されるものとされないもの」という区分け
N = int(input())
P = [int(input()) for i in range(N)]

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

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

print(N - k)

Submission status: Wrong Answer

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

cnt = N
for e in reversed(P):
    if e == cnt:
        cnt -= 1

ans = cnt

cnt = 1
for e in P:
    if e == cnt:
        cnt += 1

ans = min(N - cnt + 1, ans)

print(ans)

Submission status: Wrong Answer

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

cnt = N
for e in reversed(P):
    if(e == cnt):
        cnt -= 1

print(cnt)

Submission status: Wrong Answer

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

    print(N - length)

sol()

Submission status: Wrong Answer

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(N):
        if index[i] < index[i + 1]:
            seq += 1
        else:
            length = max(length, seq)
            seq = 1

    print(N - length)

sol()

Submission status: Wrong Answer

Solution code:
N = int(input())
L = []
for i in range(N):
    L.append(int(input()))
 
def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
 
print(N - LIS(L))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from collections import defaultdict, deque
import math
from math import factorial
import fractions
import re

BIGNUM = 10 ** 9 + 7

def main():
    #A, B, C, K = map(int, input().split())

    N = int(input())

    pos = {}
    for i in range(N):
        p = int(input())
        pos[p-1] = i

    maxnum = 0
    for i in range(N-1):
        if pos[i] > pos[i+1]:
            break
    maxnum = i

    for i in range(N-1):
        if pos[N-i-1] < pos[N-i-2]:
            break

    if maxnum < i:
        maxnum = i

    maxnum += 1
    print(N - maxnum)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a = 0
b = n+1

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

print(min(b-1,n-a))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[int(input()) for i in range(n)]
x=0
for i in l:
    if i==x+1:x+=1
y=n
for i in l[::-1]:
    if i==y:y-=1
print(min(n-x,y))

Submission status: Wrong Answer

Solution code:
n=int(input())
P=[]
for i in range(n):
  P.append(int(input()))
cur=1
for i in range(n):
  if P[i]==cur:
    cur+=1
l=cur-1
cur=n
for i in range(n):
  if P[n-1-i]==cur:
    cur-=1
r=n-cur
print(n-max(l,r))

Submission status: Wrong Answer

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 pp, p in zip(pn, pn[1:]):
  if pp < p:
    tmpk += 1
  else:
    k = k if k > tmpk else tmpk
    tmpk = 1

print(n - k)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [int(input()) for _ in range(n)]
target = 1
for i in range(n):
    if p[i] == target:
        target += 1
ans = n - target + 1
target = n
for i in reversed(range(n)):
    if p[i] == target:
        target -= 1
ans = min(ans, target)
print(ans)

Submission status: Wrong Answer

Solution code:

n=int(input())
p=[0]*n
for i in range(n):
    p[i]=[int(input()),i]

p=sorted(p,key=lambda x:x[0])
#print(p)
cnt=1
pre=p[0][1]
ans=0
for i in range(1,n):
    x=p[i][1]
    if x>pre:
        cnt+=1
    else:
        cnt=1
    pre=x
    ans=max(ans,cnt)

print(n-ans)

Submission status: Wrong Answer

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(max(dp)+1)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
L = []
for i in range(N):
  L.append(int(input()))
dp = [float('inf')]*N
for i in range(N):
  k = bisect.bisect_left(dp,L[i])
  dp[k] = L[i]
cnt = 0
for i in range(N):
  if dp[i] != float('inf'):
    cnt += 1
  else:
    break
print(N-cnt+1)

Submission status: Wrong Answer

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

c = 1
c2 = N
for i in range(N):
  if P[i] == c:
    c += 1
  if P[-1 -i] == c2:
    c2 -= 1

c = N - c + 1
print(min(c, c2))

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))

dp = [0]*(N+1)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for i in range(N)]
t = 1
for a in P:
    if a == t:
        t += 1
ans = N+1-t

t = N
for a in P[::-1]:
    if a == t:
        t -= 1
ans = min(ans, t)

print(ans)

Submission status: Wrong Answer

Solution code:
a = int(input())
s = 1
r = 0
k = []
for i in range(a):
    t = int(input())
    if s == t:
        s+=1
        r+=1
    k.append(t)
p = a
k = k[::-1]
c = 0
for i,m in enumerate(k):
    if p == m:
        p-=1
        c+=1
#print(a-r,a-c)
print(min((a-r),(a-c)))

Submission status: Wrong Answer

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

L = sorted(L,key=lambda x:x[1])

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

Submission status: Wrong Answer

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

L = sorted(L,key=lambda x:x[1])

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
l=np.zeros(n)
lg=np.zeros(n)
for i in range(n):
    l[i]=int(input())
    lg[n-1-i]=n+1-l[i]
a=np.argsort(l)
ag=np.argsort(lg)
ans=0
ansg=0
for i in range(n-int(l[0])):
    if a[i+int(l[0])-1]>a[i+int(l[0])]:
        ans+=1
if ans>0:
    ans+=1
    
for i in range(n-int(lg[0])):
    if ag[i+int(lg[0])-1]>ag[i+int(lg[0])]:
        ansg+=1
if ansg>0:
    ansg+=1
print(min(int(l[0])-1+ans,int(lg[0])-1+ansg))

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
l=np.zeros(n)
for i in range(n):
    l[i]=int(input())
a=np.argsort(l)
ans=0
for i in range(n-int(l[0])):
    if a[i+int(l[0])-1]>a[i+int(l[0])]:
        ans+=1
if ans>0:
    ans+=1
print(int(l[0])-1+ans)

Submission status: Wrong Answer

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):
    print(i)
    if Q[i] > Q[i - 1]:
        dp[i] = dp[i - 1] + 1

print(N - max(dp))

Submission status: Wrong Answer

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 = [0] * (N + 1)
for i in range(1, N):
    if Q[i] > Q[i - 1]:
        dp[i] = dp[i - 1] + 1
    else:
        dp[i] = 1

print(N - max(dp))

Submission status: Wrong Answer

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

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

print(N - dp[-1])

Submission status: Wrong Answer

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
print(n-cresc)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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
print(n - res)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [int(input()) for _ in range(n)]
res = n
# 前から1,2,3,...
num = 1
for i in p:
	if i == num:
		num += 1
res = min(res, n + 1 - num)
# 後ろからn,n-1,n-2,...
num = n
for i in p[::-1]:
	if i == num:
		num -= 1
res = min(res, num)
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
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: Wrong Answer

Solution code:
N=int(input())
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
  else:
    if s<a[i]:
      l+=1
    else:
      ans=max(ans,l)
      l=1
  s=a[i]
print(N-ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
p = []
ss = int(input())
p.append(ss)

for i in range(N-1):
    ss = int(input())
    p.append(ss)
    ans = max(ans, abs(p[i+1]-p[i]))
    # print(ans)

print(ans)

Submission status: Wrong Answer

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

print(N - ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
  
cnt1 = 0
wk = 1
for i in range(N):
  if A[i] == wk:
    wk += 1
    cnt1 += 1

cnt2 = 0
wk = N
for i in range(N):
  if A[N-i-1] == wk:
    wk -= 1
    cnt2 += 1
    
print(N-max(cnt1,cnt2))

Submission status: Wrong Answer

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
print(n-ans)

Submission status: Wrong Answer

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(max(chain))

Submission status: Wrong Answer

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


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

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

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
print(n-m)

Submission status: Wrong Answer

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


    print N - max_count


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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-ans)

Submission status: Wrong Answer

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+1:
        b.append(k)

print(n-max(b))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [int(input()) for i in range(N)]
for i in range(N):
    if N-i-1 ==0:
        print(0)
        exit()
    if data.index(N-i) < data.index(N-i-1):
        print(N-i-1)
        exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [int(input()) for i in range(N)]
try:
    for i in range(N):
        if data.index(N-i) < data.index(N-i-1):
            print(N-i-1)
            break
except:
    print(0)

Submission status: Wrong Answer

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

front = 0
back = 0

while True:
	if front == n - 1:
		break
	elif indeces[front] < indeces[front + 1]:
		front += 1
	else:
		break

while True:
	if back == n - 1:
		break
	elif indeces[-(back + 1)] > indeces[-(back + 2)]:
		back += 1
	else:
		break

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

Submission status: Wrong Answer

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
if n == 0:
  maxi = 0
print(n - maxi)

Submission status: Wrong Answer

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
print(n - maxi)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=n
l=0
r=0
for j in range(n):
	if (n-j) in p[:pos]:
		pos = p[:pos].index(n-j)
	else:
		r = n-j
		break
pos=0
for k in range(n):
	if k+1 in p[pos:]:
		pos += p[pos:].index(k+1)
	else:
		l = n-k
		break
if r>l:
	print (l)
else:
	print (r)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=n
for j in range(n):
	if (n-j) in p[:pos]:
		pos = p[:pos].index(n-j)
	else:
		print(n-j)
		break

Submission status: Wrong Answer

Solution code:
from itertools import count
from itertools import chain

def gen_check_numbers(n):
    center = n // 2
    l2 = chain.from_iterable(zip(reversed(range(1, center + 1)), range(center + 1 , n + 1)))
    return l2

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

    ans = 0
    center = n // 2
    for i in gen_check_numbers(n):
        print(i)
        i1 = l.index(i)
        if i <= center:
            i2 = l.index(i + 1)
            if( i2 < i1):
                l.remove(i)
                l.insert(0,i)
                ans += 1
        else:
            i2 = l.index(i - 1)
            if( i1 < i2):
                l.remove(i)
                l.append(i)
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import count
from itertools import chain

def gen_check_numbers(n):
    center = n // 2
    l2 = chain.from_iterable(zip(reversed(range(1, center + 1)), range(center + 1 , n + 1)))
    return l2

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

    ans = 0
    center = n // 2
    for i in gen_check_numbers(n):
        print(i)
        i1 = l.index(i)
        if i <= center:
            i2 = l.index(i + 1)
            if( i2 < i1):
                l.remove(i)
                l.insert(0,i)
                ans += 1
        else:
            i2 = l.index(i - 1)
            if( i1 < i2):
                l.remove(i)
                l.append(i)
                ans += 1
    print(ans, l)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
print N - longest_length

Submission status: Wrong Answer

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 = 0
last_number = -1
for i in xrange(N):
	if Q[i] > last_number:
		length_of_sequence += 1
		last_number = Q[i]
	else:
		longest_length = max(longest_length, length_of_sequence)
		length_of_sequence = 1
		last_number = Q[i]
print N - longest_length

Submission status: Wrong Answer

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 = 0
last_number = N+1
for i in xrange(N):
	if Q[i] > last_number:
		length_of_sequence += 1
		last_number = Q[i]
	else:
		longest_length = max(longest_length, length_of_sequence)
		length_of_sequence = 1
		last_number = Q[i]
print N - longest_length

Submission status: Wrong Answer

Solution code:
N = input()
P = []
for i in xrange(N):
	P.append(input())
x = 1
y = N
for i in xrange(N):
	if P[i] == x:
		x = x + 1
	if P[-i-1] == y:
		y = y - 1
print min(N+1-x, y)

Submission status: Wrong Answer

Solution code:
N = input()
P = []
for i in xrange(N):
	P.append(input())
x = 1
y = N
for i in xrange(N):
	if P[i] == x:
		x = x + 1
	if P[-i] == y:
		y = y - 1
print min(N+1-x, y)

Submission status: Wrong Answer

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-count-1

Submission status: Wrong Answer

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

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

print(N - maxcnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = 0

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

print(N - max(num, ans))

Submission status: Wrong Answer

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 = 0

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

print(N - max(num, ans))

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
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 - maxl)

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

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

Submission status: Wrong Answer

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

cnt = 0
first = p[0]
last = p[-1]
for i in range(n):
    if first > p[i]:
        cnt += 1
        first = p[i]
for i in range(n):
    if last < p[i]:
        cnt += 1
        last = p[i]

if p[0] == last:
    cnt += n - p[0] - 1
print(cnt)

Submission status: Wrong Answer

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

print(n - result)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

dic = {p[0]:1}
for i in range(1,n):
    print(dic)
    check = 0
    for k in list(dic):
        #print(k, dic[k])
        if p[i] == k + dic[k]:
            dic[k] += 1
            check = 1
            break
        elif p[i] == k - 1:
            dic[p[i]] = 1
            if dic[k] < max(dic.values()) or dic[k] == 1:
                dic.pop(k)
        else:
            dic[p[i]] = 1
            
print(n - max(dic.values()))

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int( input() )

P = np.array([0]*N)
Q = np.array([0]*N)

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

q = Q[0]
count = 1

ls = []

for i in range(N-1):
    q_ = Q[i+1]
    if q < q_:
        count += 1
        q = q_
    
    elif count != 1:
        ls.append(count)
        count = 1
        
ls.append(count)

M = max(ls)
print(N-M)

Submission status: Wrong Answer

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

for i in range(n-1):
    if b+1!=a[i+1]:
        count+=1
    else:
        b+=1

print(count)

Submission status: Wrong Answer

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] > 0:
        cnt += 1
    else:
        max_cnt = max(max_cnt, cnt)
        cnt = 1
print(N - max_cnt)

Submission status: Wrong Answer

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

if N==1:
    print(1)
else:
    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

    print(N-tmp)

Submission status: Wrong Answer

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

print(N-tmp)

Submission status: Wrong Answer

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

result = 0
i = 1
count = 0
index = 0
while i <= n:
    
    if i in list[index:]:
        index = list.index(i)
        count += 1
        i += 1
    else:
        index = 0
        if count > result:
            result = count
        count = 0

print( n - result)

Submission status: Wrong Answer

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]

print(n-max_cnt)

Submission status: Wrong Answer

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 = 0
qpre = 0
 
for i in range(n):
    if q[i] > qpre:
        cnt += 1
    else:
        if max_cnt < cnt:
            max_cnt = cnt
        cnt = 1
    qpre = q[i]

print(n-max_cnt)

Submission status: Wrong Answer

Solution code:
da = int(input())
k = [0]*da
max = 0
l = 0
for i in range(da):
  k[i] = int(input())

for i in range(da):
  p = k[i]
  for j in range(1,da - i - 1):
    if k[i+j] == p + 1:
      p += 1
      l += 1
  if max <= l:
    max = l

print(da - 1- max)