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())
n_list = []
for i in range(N):
    n_list.append(tuple([int(input()), i]))
n_list_idx = [0 for _ in range(N + 1)]
for n in n_list:
    n_list_idx[n[0]] = n[1]
o_max = 0
o = 0
for i in range(1, 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
print(N - o_max)

Submission status: Wrong Answer

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
    else:
        M = max(M, cnt)
        cnt = 1

print(N-M)

Submission status: Wrong Answer

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

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

main()

Submission status: Wrong Answer

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

    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)

Submission status: Wrong Answer

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

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

Q=[0]*(N+1)

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

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

print(N-Ans)

Submission status: Wrong Answer

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

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


def editorial(N, P):
    if N == 1:
        print(0)
        return

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

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
    if i == N - 1:
        subset_num = max(subset_num, num)
print(N - subset_num)

Submission status: Wrong Answer

Solution code:
N = int(input())
Q = [0]*N
for i in range(N):
        Q[int(input())-1] = i
subset_num = 0
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:
    subset_num = max(subset_num, num)
print(N - subset_num)

Submission status: Wrong Answer

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

N = int(input())
P = [int(input()) for _ in range(N)]
Q = [P.index(i) for i in range(1, N + 1)]

subset_num = 0
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:
    subset_num = max(subset_num, num)
print(N - subset_num)

Submission status: Wrong Answer

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

N = int(input())
P = [int(input()) for _ in range(N)]
Q = [P.index(i) for i in range(1, N + 1)]

subset_num = 0
num = 0
for i in range(N-2):
    num += 1
    if Q[i] > Q[i+1]:
        subset_num = max(subset_num, num)
        num = 0
    if i == N-3:
        subset_num = max(subset_num, num)
print(N - subset_num)

Submission status: Wrong Answer

Solution code:
N = int(input())

count = 0
q = int(input())
count += q-1
q += 1
for i in range(N-1):
    p = int(input())
    if p == q+1:
        q += 1
    elif p > q+1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

count = 0
q = int(input())
q += 1
count += q-1
for i in range(N-1):
    p = int(input())
    if p == q+1:
        q += 1
    elif p > q+1:
        count += 1
print(count)

Submission status: Wrong Answer

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

print(N-1-ansr)

Submission status: Wrong Answer

Solution code:
N = int(input())

count = 0
q = int(input())
count += q-1
for i in range(N-1):
    p = int(input())
    if p == q+1:
        q += 1
    elif p > q+1:
        count += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

count = 0
q = int(input())
count += q-1
for i in range(N-1):
    p = int(input())
    if p == q+1:
        q += 1
    elif p > q+1:
        count += 1
        q += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
n = 0
m = N
for pi in P:
    if n + 1 == pi:
        n += 1
        if n == m:
            break
    else:
        if m > pi:
            m = pi
n1 = N - n

n = N + 1
m = 1
for pi in P[::-1]:
    if n - 1 == pi:
        n -= 1
        if n == m:
            break
    else:
        if m < pi:
            m = pi
n2 = n - 1
print(min(n1, n2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if cnt != 1:
	ans = cnt
print(N-ans)

Submission status: Wrong Answer

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

print(N-ans)

Submission status: Wrong Answer

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

numf = N+1
for i in range(1,N+1):
        if i == 1:
                pf = P.index(i)
        else:
                nf = P.index(i)
                if nf - pf < 0:
                        numf = i
                        break
                else:
                        pf = nf

numb = N+1
for i in range(1,N+1):
        if i == 1:
                pb = P.index(N+1-i)
        else:
                nb = P.index(N+1-i)
                if pb - nb < 0:
                        numb = i
                        break
                else:
                        pb = nb

print(N+1 - max(numf,numb))

Submission status: Wrong Answer

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

print(N-ans)

Submission status: Wrong Answer

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]:
        lmax = max(lmax,length)
        length = 1
    else:
        length += 1

print(n - length)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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(n):
    if a[i] < a[i-1]:
        lmax = max(lmax,length)
        length = 1
    else:
        length += 1

print(n - length)

Submission status: Wrong Answer

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

print(N-cnt)

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
tl = 0
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: Wrong Answer

Solution code:
n = int(input())
seq = []
for i in range(n):
  k=int(input())
  seq.append(k)
i=0
count =0
while i<n:
  j=i+1
  while j<n:
    if seq[j]-seq[i]==j-i:
      count = count + 1
    j=j+1
  i=i+1

print(n-count)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
tl = 0
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:
        tl = max(tl, tmp)
        tmp = 1

ans = n - tl
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*N
cnt = 0
for i in range(N):
	a[i] = int(input())
	if i != 0 and a[i] - a[i-1] == 1:
		cnt += 1

print(N-2-cnt)

Submission status: Wrong Answer

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)] 
a1=0
a2=0
k = 1
for i in range(n):
    if t[i]==k:
        a1 = a1 + 1
        k = k+1
k = n
for i in range(n):
    if t[n-i-1]==k:
        a2 = a2 + 1
        k = k-1

print(n - max(a1,a2))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]
c = 0
maxc = 0
for i in range(1,N):
    if a.index(i) < a.index(i+1):
        c += 1
    else:
        if c > maxc:
            macxc = c
        c = 0
print(N-maxc)

Submission status: Wrong Answer

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)] 
a1=n
a2=n
k=1
for i in range(n):
    if t[i]==k:
        a1 = a1 - 1
        k = k+1
k = n
for i in range(n-1,-1,-1):
    if t[i]==k:
        a2 = a2 - 1
        k = k-1

print(min(a1,a2))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
A=[int(input())-1 for i in range(n)]

d=set()
for i in range(n):
    d.add(i-A[i])
print(len(d))

Submission status: Wrong Answer

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=n+2
k=1
for i in range(n):
    if t[i]==k:
        a = a-1
        k = k+1
k = n
for i in range(n-1,-1,-1):
    if t[i]==k:
        a = a-1
        k = k-1

print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
d = {0:-1}
Flag = True
n = 0
m = 0
for i in range(N):
    d[int(input())] = i
for i in range(N)[::-1]:
    if i == N-1:
        if d[i+1] < d[i]:
            n += 1
    else:
        if d[i+1] < d[i]:
            n += i
            break

for i in range(1,N):
    if i == 1:
        if d[i+1] < d[i]:
            m += 1
    else:
        if d[i+1] < d[i]:
            m += N-i+1
            break
print(min(n,m))

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
a = [int(input()) for i in range(N)]
c = 1
d = 1
e = 1
f  = 1
ushi = 1
mae = 1
for i in range (1,N-1):
  ti = a.index(i)
  dai = a.index(i+1)
  ti2 =  a.index(N-i  + 1)
  dai2  =  a.index(N - i)
  if  ti  < dai:
      e  += 1
  else:
    mae =  max(e,mae)
    e = 1
  if  ti2  < dai2:
     f += 1
  else:
    ushi = max(f,ushi)
    f = 1
zen = ushi + mae
kota = N - max(mae,ushi)
print(kota)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

N=input()
LIS = []

for x in range(0,N):
	y = input()
	z = bisect.bisect_left(LIS, y)
	if z >= len(LIS):
		LIS.append(y)
	else:
		LIS[z]=y

print len(LIS)+1

Submission status: Wrong Answer

Solution code:

N = input()

NN = []

for i in range(N):
    tmp = [input(), i+1]    
    NN.append(tmp)

NN.sort(key=lambda x:x[0])

tmp = range(N-1, 0, -1)

count = 0
flag = 0

for i in tmp:
    now_n = NN[i]
    next_n = NN[i-1]
    if flag == 0:
        if now_n[1] < next_n[1]:
            count = count + 1
        else:
            flag = 1
    else:
        if now_n[1] < next_n[1]:
            count = count + i
            break
        
print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
d = {0:-1}
Flag = True
n = 0
m = 0
for i in range(N):
    d[int(input())] = i
n = 0
for i in range(N)[::-1]:
    if i == N-1:
        if d[i+1] < d[i]:
            n += 1
    else:
        if d[i+1] < d[i]:
            n += i
            break

for i in range(N):
    if i == 0:
        if d[i+1] < d[i]:
            m += 1
    else:
        if d[i+1] < d[i]:
            m += N-i+1
            break
print(min(n,m))

Submission status: Wrong Answer

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

lltr = [False for x in range(n-1)]
for i in range(1, n):
    if n2i[i] < n2i[i+1]:
        lltr[i-1] = True
for i in range(n-1):
    tmp = 1
    for j in range(i, n-1):
        if lltr[j]:
            tmp += 1
        else:
            break
    tl = max(tl, tmp)
ans = n - tl
print(ans)

Submission status: Wrong Answer

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]=1
    if ai + 1 in al.keys():
      del al[ai]
print(n-ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
def xxx(arr,t):
    exp=t 
    for i in range(t):
        if arr[i]==exp:
            exp-=1 
    return exp
for _ in range(n):
    l.append(int(input()))
m=l[::-1]
p=xxx(l,n)
q=xxx(m,n)
print(min(p,q))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = [0 for _ in range(N)]
    for i in range(N):
        P[i] = int(input())
    count = [0 for _ in range(N)]
    C = 0
    for i in range(N):
        count[i] = (P[i]-1) - i
        if count[i] > 0:
            C+=count[i]
    return min(C, N)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input())]
minP = P[0]
addlist = []
dellist = []
for i in range(1, N):
    P.append(int(input()))
    if minP > P[i]:
        addlist.append(P[i])
        dellist.append(i)
    else:
        minP = P[i]

#for i in range(len(dellist)):
 #  del P[dellist[i] - i]
    
addlist = sorted(addlist)
P = addlist + P
cnt = 0
j = 0
key = len(addlist)
l = 1
for i in range(N):
    if j < len(dellist):
        if i == dellist[j] + key:
            j += 1
            l -= 1
        elif P[i] != l:
            cnt += 1
    elif P[i] != l:
        cnt += 1
    l += 1
print(len(addlist) + int(cnt / 2))

Submission status: Wrong Answer

Solution code:
N = int(input())

nums = []

for i in range(N):
	num = int(input())
	nums.append(num)

front = 1
back = N

front_num = 0
back_num = 0
for i in range(N):
	if nums[i] == front:
		front_num += 1
		front += 1
	if nums[N-i-1] == back:
		back_num += 1
		back -= 1

print(N - max(front_num,back_num))

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = []
for j in range(n):lis.append(int(input()))
co = n-1
cou = n-1
for i in range(n-1):
	if lis.index(n-i) > lis.index(n-(i+1)):cou -= 1
	else:break
for k in range(n-1):
	if lis.index(k+2) > lis.index(k+1):co -= 1
	else:break
print(min(co,cou))

Submission status: Wrong Answer

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

al= defaultdict(lambda: 0)
ds=[]
ans=0
for ai in a:
  ds.append(ai)
  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]=1
    if ai + 1 in al.keys():
      del al[ai+1]
print(n-ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
d = {0:-1}
Flag = True
n = 0
m = 0
for i in range(N):
    d[int(input())] = i
n = 0
for i in range(N)[::-1]:
    if d[i+1] < d[i]:
        n = i
        break

for i in range(N):
    if d[i+1] < d[i]:
        m = N-i+1
        break
print(min(n,m))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = [0 for _ in range(N)]
    for i in range(N):
        P[i] = int(input())
    count = [0 for _ in range(N)]
    C = 0
    for i in range(N):
        count[i] = (P[i]-1) - i
        if count[i] > 0:
            C+=count[i]
    return C

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

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = []
for i in range(n):
	a = int(input())
	lis.append(a)
co = n-1
cou = n-1
for i in range(n-1):
	if lis.index(n-i) > lis.index(n-(i+1)):
		cou -= 1
	else:break
for k in range(n-1):
	if lis.index(k+2) > lis.index(k+1):
		co -= 1
	else:break
print(min(co,cou))

Submission status: Wrong Answer

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

flg = 0
ma = (mi)
new = []
for i in range(N-1,-1,-1):
	if flg == 0 and a[i] > mi:
		ma = a[i]
		flg = 1
	if mi < a[i] and a[i] < ma:
		new.append(a[i])

ans += (N - ma)
new.reverse()
l = len(new)
if l == 1:
	print(ans)
	exit(0)

for i in range(l-1):
	if new[i+1] < new[i]:
		ans += 1

print(ans+1)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = [0 for _ in range(N)]
    A = [i+1 for i in range(N)]
    for i in range(N):
        P[i] = int(input())
    count = [0 for _ in range(N)]
    C = 0
    for i in range(N):
        count[i] = A.index(P[i]) - i
        if count[i] > 0:
            C+=count[i]
    return C

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

Submission status: Wrong Answer

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
    if(f==0):
      maxi=d[a[i]]
    else:
      if(d[a[i]]>maxi):
        maxi=d[a[i]]
  else:
    d[a[i]]=1

print(n-maxi)

Submission status: Wrong Answer

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
    if(f==0):
      maxi=d[a[i]]
    else:
      if(d[a[i]]>maxi):
        maxi=d[a[i]]
  else:
    d[a[i]]=0
print(n-maxi-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input())]
minP = P[0]
addlist = []
dellist = []
for i in range(1, N):
    P.append(int(input()))
    if minP > P[i]:
        addlist.append(P[i])
        dellist.append(i)
    else:
        minP = P[i]

for i in range(len(dellist)):
   del P[dellist[i] - i]
    
addlist = sorted(addlist)
P = addlist + P
cnt = 0

print(P)
for i in range(N):
    if P[i] != i + 1:
        cnt += 1
print(len(addlist) + int(cnt / 2))

Submission status: Wrong Answer

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

Solution code:
N = int(input())
d = {0:-1}
Flag = True
for i in range(N):
    d[int(input())] = i
n = 0
for i in range(N)[::-1]:
    if d[i+1] < d[i]:
        Flag = False
        print(i)
        break
if Flag:
    print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = []
forward = 0
back = n+1
ans1 = 0
ans2 = 0
for i in range(n):
    P = int(input())
    p.append(P)
for i in range(0,n):
    if forward + 1 == p[i]:
        forward = p[i]
        ans1 += 1
for i in range(n-1,-1,-1):
    if back - 1 == p[i]:
        back = p[i]
        ans2 += 1
print(min(n-ans1,n-ans2))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input())]
minP = P[0]
addlist = []
dellist = []
for i in range(1, N):
    P.append(int(input()))
    if minP > P[i]:
        addlist.append(P[i])
        dellist.append(i)
    else:
        minP = P[i]
Psort = [i for i in range(1, N + 1)]

for i in range(len(dellist)):
   del P[dellist[i] - i]
    
addlist = sorted(addlist)
P = addlist + P
cnt = 0

print(P)
for i in range(len(Psort)):
    if P[i] != Psort[i]:
        cnt += 1
print(len(addlist) + int(cnt / 2))

Submission status: Wrong Answer

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

count = 0
for i in range(N-1):
    if number[i] > number[i+1]:
        count = count + 1
        
print(count+1)

Submission status: Wrong Answer

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

M1=(N+1)//2
M2=(N+2)//2
p=0
t=N
c=M2
K=0
L=0
while c<=N:
    while P[p]!=c:
        if P[p]>c:
            t=min(t,P[p])
        p+=1
    if t==c+1:
        K=c+1
        c=N+1
    else:
        c+=1
j=N-1
s=1
d=M1
while d>0:
    while P[j]!=d:
        if P[j]<d:
            s=max(s,P[j])
        j-=1
    if s==d-1:
        L=d-1
        d=-1
    else:
        d-=1
print(N+1-K+L)

Submission status: Wrong Answer

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

t1,step1 = P[0],0
for i in range(N):
    if P[i]==t1:
        t1 += 1
        continue
    step1 += 1

t2,step2 = P[N-1],0
for i in range(N):
    if P[N-1-i]==t2:
        t2 -= 1
        continue
    step2 += 1

print(min(step1,step2))

Submission status: Wrong Answer

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


kai1 = n -1
kai2 = n -1
for j in range(1,n,1):
    if t.index(j) < t.index(j+1):
        kai1 -= 1
    else:
        break
    #
for j in range(n,1,-1):
    if t.index(j) > t.index(j-1):
        kai2 -= 1
    else:
        break

#print(kai1,kai2)

print(min(kai1,kai2))

Submission status: Wrong Answer

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

front = []
back = []
for n in numbers:
    if n <= N/2:
        front.append(n)
    else:
        back.append(n)

front_count = len([x for x in front if front[0] > x])
back_count = len([x for x in back if back[-1] < x])
print(front_count + back_count)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = [0 for _ in range(N)]
    A = [i+1 for i in range(N)]
    for i in range(N):
        P[i] = int(input())

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

    if N%2==0:
        if N==2:
            if P[0]>P[1]:
                return 1
            else:
                return 0
        a = P.index(N//2)
        b = P.index(N//2+1)
        if a<b:
            if (P[0]==N//2+2)and(P[1]==N//2-1):
                return min(N-3, K)
            elif (P[-1]==N//2-1)and(P[-2]==N//2+2):
                return min(N-3, K)
            elif (P[0]==N//2-1)and(P[-1]==N//2+2):
                return min(K, N-4)
            elif (P[0]==N//2-1)or(P[-1]==N//2+2):
                return min(K, N-3)
            else:
                return min(K, N-2)
        else:
            if (P[0]==N//2+2)and(P[1]==N//2-1):
                return min(K, N-2)
            elif (P[-1]==N//2-1)and(P[-2]==N//2+2):
                return min(K, N-2)
            elif (P[0]==N//2-1)and(P[-1]==N//2+2):
                return min(K, N-2)
            elif (P[0]==N//2-1)or(P[-1]==N//2+2):
                return min(K, N-2)
            else:
                return min(K, N-1)
    else:
        if N==1:
            return 0
        elif (P[0]==N//2+2)and(P[1]==N//2):
            return min(K, N-2)
        elif (P[-1]==N//2)and(P[-2]==N//2+2):
            return min(K, N-2)
        elif (P[0]==N//2)and(P[-1]==N//2+2):
            return min(K, N-3)
        elif (P[0]==N//2)or(P[-1]==N//2+2):
            return min(K, N-2)
        else:
            return min(K, N-1)

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

Submission status: Wrong Answer

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

import os
import sys
import math
import numpy as np


def calc_left(arr_left):
    var = max(arr_left)
    ans = var - 1

    ind = arr_left.index(var)
    for x in arr_left[:ind][::-1]:
        if x == var - 1:
            var = x
            ans -= 1

    return max(0, ans) # var - 1


def calc_right(arr_right):
    var = min(arr_right)
    ans = N - var

    ind = arr_right.index(var)
    for x in arr_right[ind:]:
        if x == var + 1:
            var = x
            ans -= 1

    return max(0, ans) # var - 1



def main():
    global N
    N = int(input())
    arr = list(map(lambda _:int(input()), range(N)))
    Ps = np.array(arr)
    ans = 0

    border = int(N/2)

    arr_left = list(Ps[Ps<=border]) # smaller half
    arr_right = list(Ps[Ps>border]) # larger half

    if N == 1:
        print(0)
        return

    if arr.index(border) > arr.index(border + 1):
        cost_left = calc_left(arr_left)
        cost_right = calc_right(arr_right)
        if cost_left < cost_right:
            _ = arr.pop(arr.index(border))
            arr.insert(0, border)
        else:
            _ = arr.pop(arr.index(border+1))
            arr.append(border+1)
        ans += 1

    Ps = np.array(arr)
    arr_left = list(Ps[Ps<=border]) # smaller half
    arr_right = list(Ps[Ps>border]) # larger half

    ans += calc_left(arr_left)
    ans += calc_right(arr_right)


    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

print(Ps)

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

Solution code:
N = int(input())

l = list(range(N))

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

# print(l)

count_l = [1]
ind_list = [0] * N

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

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

print(N - max(count_l))