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 os
import sys
import math
import numpy as np


def calc_left(arr_left):
    # if len(arr_left) < 2:
    #     return 0
    # ### arr_left
    # border = var
    # ind = arr_left.index(var)

    # while border >= var > 1:
    #     # ind = np.where(arr_left == var)
    #     ind_smaller = arr_left.index(var - 1)
    #     if ind_smaller > ind:
    #         break
    #     else:
    #         var -= 1
    #         ind = ind_smaller
    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 ans # var - 1


def calc_right(arr_right):
    # if len(arr_right) < 2:
    #     return 0
    # ### arr_right
    # border = var

    # ind = arr_right.index(var)

    # while N-1 >= var >= border:
    #     # ind = np.where(arr_right == var)
    #     ind_larger = arr_right.index(var + 1)
    #     if ind_larger < ind:
    #         break
    #     else:
    #         var += 1
    #         ind = ind_larger

    # # ans += (N - var)
    # return N - var

    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 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(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
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:
        break;

now_pos = p_hash[N]
count_2 = 1
for j in range(1,N):
    pos_new = p_hash[N-j]
    if pos_new < now_pos:
        count_2 += 1
        now_pos = pos_new
    else:
        break;

count = max(count_1, count_2)

print(N - count)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
for i in range(N):
	dic[int(input())]=i
	
p = {0:0}
q = {0:0}
P = 0
Q = 0
l = 1
for i in range(N-1):
	
	if dic[i+1]>dic[i+2]:
		p[l] = i+1 - p[l-1]
		l = l + 1
	if i == N-2:
		p[l] = N-p[l-1]
	
	
m = 1
for j in range(N-1):
	if dic[N-j]<dic[N-1-j]:
		q[m] = j+1 - q[m-1]
		m = m+1
	if i == N-2:
		q[m] = N - q[m-1]

for i in range(l):
	if P < p[i]:
		P = p[i]	

for i in range(m):
	if Q < q[i]:
		Q = q[i]
u = min(N-P,N-Q)
print(u)

Submission status: Wrong Answer

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


def func(l, start=1, rev=False):
    stride = 1 if not rev else -1

    if (len(l) != 0) and (start in l):
        return 1 + func(l[l.index(start)+1:], start + stride, rev)
    else:
        return 0


res1 = n - func(ps)
res2 = n - func(ps[::-1], start=n, rev=True)

print(res1 if res1 < res2 else res2)

Submission status: Wrong Answer

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

m=0
z=0
s=0
s_next=0
for i in range(N):
    s_next = L.index(i+1)
    if s < s_next:
        z += 1
    else:
        m = max(m, z)
        z=1
    s = s_next

print(N-m)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
    if p[i] == 1:
        sitai = i
    if p[i] == n:
        uei = i
sita = 1
ue = n
csita = 1
cue = 1
for i in range(n):
    if sitai < i and p[i] == sita+1:
        sitai = i
        sita = p[i]
        csita += 1
    if n-1-i < uei and p[n-1-i] == ue-1:
        uei = n-1-i
        ue = p[n-1-i]
        cue += 1
print(min(n-csita,n-cue))

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

    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 N-3
            elif (P[-1]==N//2-1)and(P[-2]==N//2+2):
                return N-3
            elif (P[0]==N//2-1)and(P[-1]==N//2+2):
                return N-4
            elif (P[0]==N//2-1)or(P[-1]==N//2+2):
                return N-3
            else:
                return N-2
        else:
            if (P[0]==N//2+2)and(P[1]==N//2-1):
                return N-2
            elif (P[-1]==N//2-1)and(P[-2]==N//2+2):
                return N-2
            elif (P[0]==N//2-1)and(P[-1]==N//2+2):
                return N-2
            elif (P[0]==N//2-1)or(P[-1]==N//2+2):
                return N-2
            else:
                return N-1
    else:
        if N==1:
            return 0
        elif (P[0]==N//2+2)and(P[1]==N//2):
            return N-2
        elif (P[-1]==N//2)and(P[-2]==N//2+2):
            return N-2
        elif (P[0]==N//2)and(P[-1]==N//2+2):
            return N-3
        elif (P[0]==N//2)or(P[-1]==N//2+2):
            return N-2
        else:
            return N-1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
seq = []
cnt_front = 1
cnt_back = N
for i in range(N):
    p = int(input())
    if cnt_front == p:
        cnt_front += 1
    seq.append(p)

for i in range(N):
    if cnt_back == seq[- i - 1]:
        cnt_back -= 1

cnt_back = N - cnt_back
if cnt_back < cnt_front:
    print(N - cnt_back)
else:
    print(N - cnt_front)

Submission status: Wrong Answer

Solution code:
n = int(input())

top = int(input())
l = 0
lr = 0
pl = top
r = 0
rl = 0
pr = top

for i in range(n - 1):
  s = int(input())
  if(s < top):
    l += 1
    if(s < pl):
      pl = s
    else:
      lr += 1
  else:
    r += 1
    if(pr < s):
      pr = s
    else:
      rl += 1

a = rl*2 + l
print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
asc = 0
desc = 0
target = 1
for i in p:
    if i == target:
        asc += 1
        target += 1

target = n
for i in reversed(p):
    if i == target:
        desc += 1
        target -= 1

ans = n - max(asc, desc)
print(ans)

Submission status: Wrong Answer

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

    idx = make_index(p)
    f = check_forward(p, idx)
    b = check_backward(p, idx)

    ans = n - max(f, b)
    print(ans)

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

def check_forward(p, idx):
    c = 0
    i = -1
    for x in range(1, len(p) + 1):
        j = idx[x]
        if j < i:
            break
        c += 1
        i = j
    return c

def check_backward(p, idx):
    c = 0
    i = len(p)

    for x in range(len(p), 0, -1):
        j = idx[x]
        if j > i:
            break
        c += 1
        i = j
    
    return c

main()

Submission status: Wrong Answer

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

Ans = 0
l = len(P)

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

if l%2==1 and P[l//2]==l//2+1:
    hl = N//2-1
    t3,step3 = 1,0
    for i in range(hl):
        if P[i]==t3:
            t3 += 1
            continue
        step3 += 1
    t4,step4 = N,0
    for i in range(hl):
        if P[N-1-i]==t4:
            t4 -= 1
            continue
        step4 += 1
else:
    step3,step4 = 10**10,10**10
print(min(step1,step2,step3+step4))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
P = [int(input()) for _ in range(N)]


def calcBackFront(P):
    N = len(P)
    counter = 0
    tmp = P[0]
    for i in range(1, N):
        if P[i] < tmp:
            continue
        elif(tmp + 1 == P[i]):
            counter += 1
        else:
            counter = 0
            tmp = P[i]
    return N - counter


print(calcBackFront(P))

Submission status: Wrong Answer

Solution code:
N = int(input())

Ps = [int(input())]
tmp, tmp_P, result = Ps[0], Ps[0], 1
for i in range(1, N):
    tmp_P = int(input())
    if tmp + 1 == tmp_P:
        result += 1
        tmp = tmp_P

    Ps.append(tmp_P)

print(N - result)

Submission status: Wrong Answer

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


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


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


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


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


def read_str():
    return input()


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, P):
    A = []
    B = []
    for p in P:
        if p <= N / 2:
            A.append(p)
        else:
            B.append(p)
    # print(A)
    # print(B)
    c = 0
    for i, a in enumerate(A):
        if a != i + 1:
            c = max(c, a - 1)
    d = 0
    for i, b in enumerate(B):
        if b != N / 2 + i + 1:
            d = max(d, N - b)

    if c + d != 0:
        return c + d

    c = 0
    d = 0
    for i, p in enumerate(P):
        if p != i + 1 and p <= N / 2:
            c = max(c, p - 1)
        elif p != i + 1 and p >= N / 2:
            d = max(d, N - p)
    return c + d


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

    print(slv(N, P))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
P = [int(input()) for _ in range(N)]


def calcBackFront(P):
    N = len(P)
    counter = 0
    tmp = P[0]
    for i in range(1, N):
        if tmp < P[i]:
            continue
        elif(tmp + 1 == P[i]):
            counter += 1
        else:
            counter = 0
            tmp = P[i]
    return N - counter


print(calcBackFront(P))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    x = int(input())
    a[x-1] = i+1
hi = 0
N = n
while hi == 0 and N != 0:
    N -= 1
    if a[N-1] > a[N]:
        hi = 1
print(N)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = []
for i in range(N):
    P.append(int(input()))
increment_count = 0
rev_increment_count = 0
for i in range(N):
    if P[i] == increment_count + 1:
        increment_count += 1
    if P[-i - 1] == N - rev_increment_count:
        rev_increment_count += 1
print(N - max(increment_count, rev_increment_count))

Submission status: Wrong Answer

Solution code:
n= int(input())
l = [int(input()) for i in range(n)]
count = 1
for _ in range(n-1):
    if l.index(n-1-_) < l.index(n-_):
        count += 1
    else:
        break
print(n - count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

N=int(input())

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

checkmin=1
for i in prog:
    if i==checkmin:
        checkmin+=1

rvprog=reversed(prog)

checkmax=N
for i in rvprog:
    if i==checkmax:
        checkmax-=1

if checkmin-1>N-checkmax:
    print(N-checkmin+1)
else:
    print(checkmax)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    x = int(input())
    a[x-1] = i+1
hi = 0
N = n
while hi == 0 and N != 0:
    N -= 1
    for i in range(n-N):
        if a[N-1] > a[n-i-1]:
            hi = 1
            break
print(N)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
bef = int(input())
small = 1
large = N
if N > 1:
    for i in range(N-1):
        now = int(input())
        if now < bef:
            small = max([now, small])
            large = min([bef, large])
        bef = now
    ans = min([small, N+1-large])
else:
    pass
print(str(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
bef = int(input())
small = 1
large = N
if N > 1:
    for i in range(N-1):
        now = int(input())
        if now < bef:
            small = max([now, small])
            large = min([bef, large])
    ans = min([small, N-large])
else:
    pass
print(str(ans))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
P = [int(input()) for _ in range(N)]


def calcBackFront(P):
    N = len(P)
    counter = 0
    tmp = P[0]
    for i in range(1, N):
        if tmp < P[i]:
            continue
        elif(tmp + 1 == P[i]):
            counter += 1
        else:
            counter = 0
    return N - counter


print(calcBackFront(P))

Submission status: Wrong Answer

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

maxSet = 0

temp = 1
i = 1
while i <= n:
    if p[i - 1] < p[i]:
        temp += 1
        i += 1
    else:
        maxSet = max(maxSet, temp)
        temp = 1
        i += 1
maxSet = max(maxSet, temp)
print(n - maxSet)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())

LIS = []

for i in range(n):
    y = int(input())
    z = bisect.bisect_left(LIS, y)
    if z >= len(LIS):
        LIS.append(y)
    else:
        LIS[z] = y

print(n - len(LIS))

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
for i in range(N):
	dic[int(input())]=i
	
p = N
q = N
for i in range(N-1):
	if dic[i+1]>dic[i+2]:
		p = i+1
		break
for j in range(N-1):
	if dic[N-j]<dic[N-1-j]:
		q = j+1
		break
u = min(N-p,N-q)
print(u)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

def main():
	n = int(input())
	ps = {int(input()):i for i in range(n)}
	#print(ps)

	out = 0
	cnt = 1
	tmp = 0
	for i in range(1, n):
		if ps[i+1] >= ps[i]:
			cnt += 1
		else:
			out = max(cnt, out)
			cnt = 1
	print(n - out)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

now_pos = p_hash[1]
count_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:
        break;

now_pos = P.index(N)
count_2 = 1
for j in range(1,N):
    pos_new = p_hash[N-j]
    if pos_new < now_pos:
        count_2 += 1
        now_pos = pos_new
    else:
        break;

count = max(count_1, count_2)

print(N - count)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
sum = 0
for i in range(n):
    if (i+1 != int(raw_input())):
        sum += 1 
print sum

Submission status: Wrong Answer

Solution code:
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
t1, t2 = 0, n + 1
c1, c2 = 0, 0
l = p.index(1)
r = p.index(n)
for i in p[l:]:
    if i == t1 + 1:
        c1 += 1
        t1 += 1
for i in reversed(p[:r + 1]):
    if i == t2 - 1:
        c2 += 1
        t2 -= 1
print(n - max(c1, c2))

Submission status: Wrong Answer

Solution code:
N = int(input())
union_find = [i for i in range(N)]
def find(n, P):
	if P[n] == n:
		return n
	else:
		x = find(P[n], P)
		P[n] = x
		return x

def append(n, P):
	P[n] = n - 1
	find(n-1, P)

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

appeared = [False for i in range(N)]
for i in range(N):
	n = P[i]
	appeared[n] = True
	if appeared[n - 1]:
		append(n, union_find)

cont = 0
for i in range(N):
	cont = max(cont, i - find(i, union_find) + 1)
print(N - cont)

Submission status: Wrong Answer

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

maxSet = 0

temp = 1
i = 1
while i < n:
    if p[i - 1] < p[i]:
        temp += 1
        i += 1
    else:
        maxSet = max(maxSet, temp)
        temp = 1
        i += 1
maxSet = max(maxSet, temp)
print(n - maxSet)

Submission status: Wrong Answer

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

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

ZOUKA=[0]*(N)

for i in range(1,N):
    r=i
    for j in range(N):
        if P[j]==r:
            r+=1
            ZOUKA[i]+=1

Ans=N-max(ZOUKA)
print(Ans)

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    P=[0]*N
    p=[False]*(N+1)
    P[0]=int(input())
    c=[False]*(N+1)
    for i in range(1,N):
        P[i]=int(input())
        c[P[i]]=True
        if c[P[i]-1]:
            p[P[i]-1] = True
    ans=0
    j=0
    for i in range(N):
        if p[i]:
            j+=1
        else:
            ans=max(ans,j)
            j=0
    ans=max(ans,j)
    print(N-ans-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
max1 = 0
max2 = 0
for _ in range(N):
    n = int(input())
    if max1 > n:
        if n > max2:
            max2 = n
    else:
        max1 = n
print(max2)

Submission status: Wrong Answer

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

maxSet = 0

temp = 1
for i in range(1, n):
    if p[i - 1] < p[i]:
        temp += 1
    else:
        maxSet = max(maxSet, temp)
        temp = 1
maxSet = max(maxSet, temp)
print(n - maxSet)

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    P=[0]*N
    p=[False]*(N+1)
    P[0]=int(input())
    for i in range(1,N):
        P[i]=int(input())
        if P[i]-1 in P[:i-1]:
            p[P[i]-1] = True
    ans=0
    j=0
    for i in range(N):
        if p[i]==True:
            j+=1
        else:
            ans=max(ans,j)
            j=0
    ans=max(ans,j)
    print(N-ans-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

max = 0

for i in range(n - 1):

    num = p[i]
    tmp = 0

    for num_i in p[i: n - 1]:

        if num + 1 == num_i:
            num += 1
            tmp += 1
    if tmp > max:
        max = tmp


print(n - 1 - max)

Submission status: Wrong Answer

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

maxSet = 0

temp = 1
for i in range(1, n):
    if p[i - 1] < p[i]:
        temp += 1
    else:
        maxSet = max(maxSet, temp)
        temp = 1

print(n - maxSet)

Submission status: Wrong Answer

Solution code:
N = int(input())

min = int(input())
max = min
T = 0
for i in range(N-1):
 B = int(input())
 if min > B:
  min = B
  T += 1
 if max < B:
  max = B

Submission status: Wrong Answer

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

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

now_pos = P.index(N)
count_2 = 1
for j in range(1,N):
    pos_new = p_hash[N-j]
    if pos_new < now_pos:
        count_2 += 1
        now_pos = pos_new
    else:
        break;

count = max(count_1, count_2)

print(N - count)

Submission status: Wrong Answer

Solution code:
def solve(N, P):
    xs = [0] * N
    for i, x in enumerate(P):
        xs[x - 1] = i
    r = 0
    c = 1
    p = N + 1
    for i, x in enumerate(xs):
        if p < x:
            c += 1
            r = max(r, c)
        else:
            c = 1
        p = x
    return N - r

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

print(solve(N, P))

Submission status: Wrong Answer

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

cnta, cntb = 0, 0
va, vb = 1, N
for i in range(N):
	if P[i] == va:
		cnta += 1
		va += 1
	if P[N-i-1] == vb:
		cntb += 1
		vb -= 1

print(N - max(cnta, cntb))

Submission status: Wrong Answer

Solution code:
N = int(input())

l = list(range(N))

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

# print(l)

left_num = 1
right_num = N
right_count = 0

for p in l:
    # print(p)
    if p == left_num:
        left_num += 1

# print(left_num - 1)
# print("--")
for pp in reversed(l):
    # print(pp)
    if pp == right_num:
        right_num -= 1
        right_count += 1

# print(right_count)
# print("--")


print(N - max(left_num - 1, right_count))

Submission status: Wrong Answer

Solution code:
N = int(input())
src = [int(input())-1 for i in range(N)]
ids = [None] * N
for i,a in enumerate(src):
    ids[a] = i

longest = seq = 1
for i1,i2 in zip(ids, ids[1:]):
    if i1 < i2:
        seq += 1
    else:
        longest = max(longest, seq)
        seq = 1
print(N - longest)

Submission status: Wrong Answer

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

f, r = 1, N

for i in range(N):
    if p[i]-f == 1:
        f += 1
for i in range(N):
    if r-p[-(i+1)] == 1:
        r -= 1
print(N-max(f, N+1-r))

Submission status: Wrong Answer

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

n = 1
for i in L:
    if i == n:
        n += 1

m = N
for i in reversed(L):
    if i == m:
        m -= 1

n = N - n + 1

print(min(n, m))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
LIS = []

for i in range(n):
    y = int(input())
    z = bisect.bisect_left(LIS, y)
    if z >= len(LIS):
        LIS.append(y)
    else:
        LIS[z] = y
print(n - len(LIS) + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = int(input())
T=0
for i in range(N-1):
 B = int(input())
 if A > B:
  T += 1
 A = B

print(T +1)

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    P=[]
    p=[False]*(N+1)
    P.append(int(input()))
    for i in range(N-1):
        P.append(int(input()))
        if P[-1]-1 in P[:-1]:
            p[P[-1]-1] = True
    ans=1
    j=0
    for i in range(N):
        if p[i]==True:
            j+=1
        else:
            ans=max(ans,j)
            j=0
    print(N-ans-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

n = 1
for i in L:
    if i == n:
        n += 1

m = N
for i in reversed(L):
    if int(i) == m:
        m -= 1

n = N - n - 1

print(min(n, m))

Submission status: Wrong Answer

Solution code:
#! -*- coding: utf-8 -*-
import numpy as np

n = int(raw_input())

p = np.zeros([n])
for i in range(n):
    p[i] = int(raw_input())

count = np.zeros([n],int)
i = 1
while i < n:
    check = i
    for j in range(n):
        if p[j] == check:
            count[i] += 1
            check += 1
    i += count[i]

#print count

#print np.max(count)

ans = n-np.max(count)

print ans

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
     a.append(input())
a=''.join(a)
b=list(reversed(range(1,n+1)))
b=[str(i) for i in b]

c=-1
count=0
for i in b:
    a=a.split(i)
    #print(i,a,c)
    a=a[0]
    if c==len(a): break
    c=len(a)
    count+=1
print(n-count)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[int(input())-1 for i in range(N)]
Q=[0 for i in range(N)]
for i in range(N):
    Q[P[i]]=i
L=0
R=0
for i in range(N-1):
    if Q[i]>Q[i+1]:
        R=N-i-1
        break
for i in range(N-1)[::-1]:
    if Q[i]>Q[i+1]:
        L=i+1
        break
print(min([L,R]))

Submission status: Wrong Answer

Solution code:


def main():
    n = int(input())
    pp = []
    for _ in range(n):
        pp.append(int(input()))
    dd = {}
    for i in range(n):
        dd[pp[i]] = i

    xx = [-1] * n
    for s in range(n - 1, -1, -1):
        if xx[s] >= 0:
            continue
        count = 1
        pre = pp[s]
        while pre + 1 in dd:
            i = dd[pre + 1]
            if xx[i] < 0:
                xx[s] = xx[i] + count
                break
            pre = pp[i]
            count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def backfront(arr):
	temp=len(arr)
	for i in range(n-1,-1,-1):
		if arr[i]==temp: temp-=1
	return temp
 
n=int(raw_input())
arr=[]
for i in range(n):
	arr.append(int(raw_input()))
print backfront(arr)

Submission status: Wrong Answer

Solution code:

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

n = 1
for i in L:
    if i == n:
        n += 1

m = N
for i in reversed(L):
    if int(i) == m:
        m -= 1

n = N - n - 1

print(min(n, m))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
     a.append(input())
a=''.join(a)
b=list(reversed(range(1,n+1)))
b=[str(i) for i in b]

c=0
count=0
for i in b:
    a=a.split(i)
    a=a[0]
    if c==len(a): break
    c=len(a)
    count+=1
print(n-count)

Submission status: Wrong Answer

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

now_pos = P.index(1)
count_1 = 1
for j in range(1,N):
    pos_new = P.index(j+1)
    if pos_new > now_pos:
        count_1 += 1
        now_pos = pos_new
    else:
        break;

now_pos = P.index(N)
count_2 = 1
for j in range(1,N):
    pos_new = P.index(N-j)
    if pos_new < now_pos:
        count_2 += 1
        now_pos = pos_new
    else:
        break;

count = max(count_1, count_2)

print(N - count)

Submission status: Wrong Answer

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

seq_f = 1
for a in src:
    if a == seq_f:
        seq_f += 1
seq_f -= 1

seq_b = N
for a in reversed(src):
    if a == seq_b:
        seq_b -= 1
seq_b += 1

ans = min(seq_b-1, N-seq_f)
print(ans)

Submission status: Wrong Answer

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

t=n
ansa=0

for i in range(n-1,-1,-1):
    if p[i]<t:
        ansa+=1
    else:
        t-=1
t=1
ansb=0
for i in range(n):
    if p[i]>t:
        ansb+=1
    else:
        t+=1


print(min(ansa, ansb))

Submission status: Wrong Answer

Solution code:
N = int(input())

L = []
max_int = 0
ans = 0
for i in range(N):
    n = int(input())
    L.append(n)
    if n > max_int:
        max_int = n
    elif n > ans:
        ans = n
        
min_int = N+1
ans2 = 0
for n in L[::-1]:
    if n < min_int:
        min_int = n
    elif (N+1-n) > ans2:
        ans2 = N+1-n
        
if ans2 < ans: ans = ans2
        
print(ans)

Submission status: Wrong Answer

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

forward = 0
backward = N+1

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

print(N - max(forward, N - backward + 1))

Submission status: Wrong Answer

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

reversed_P = P[:]
reversed_P.reverse()
counter_A = 0
biggest = N

for i in reversed_P:
    if i == biggest:
        counter_A += 1
        biggest -= 1


smallest = 1
counter_B = 0

for i in P:
    if i == smallest:
        counter_B += 1
        smallest += 1

print(min(N - counter_A, N - counter_B))

Submission status: Wrong Answer

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

t=n
ans=0

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

Submission status: Wrong Answer

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

seq_f = 1
for a in src:
    if a == seq_f:
        seq_f += 1
seq_f -= 1

seq_b = N
for a in reversed(src):
    if a == seq_b:
        seq_b -= 1
seq_b += 1

ans = min(seq_b, N-seq_f-1)
print(ans)

Submission status: Wrong Answer

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

start = 1
end = n

x = 1
for i in p:
    if i == x:
        x += 1

y = n
for idx in range(len(p)-1, -1, -1):
    i = p[idx]
    if i == y:
        y -= 1

s = max(x-1, n-y)
print n-s

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
INF = float('inf')
dp = [INF]*(n+1)
dp[0] = -INF
def bisec(lis,i):
    low = 0
    high = len(lis)-1
    t = (low+high)//2
    while low <= high:
        if i==lis[t]:
            break
        elif (i > lis[t]):
            low = t + 1
        elif (i < lis[t]):
            high = t - 1
        t = (low+high)//2
    return t
for i in range(1,n+1):
    if dp[i-1] < a[i-1]:
        dp[i] = a[i-1]
    pos = bisec(dp,a[i-1])
    if dp[pos] < a[i-1]:
        dp[pos+1] = a[i-1]
    else:
        dp[pos] = a[i-1]
for i in range(len(dp)-1,-1,-1):
    if dp[i] != INF:
        print(n+1-i)
        break

Submission status: Wrong Answer

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

def solve():
    # asc
    asc_num = 0
    target = 1
    for P_i in P:
        if P_i == target:
            target += 1
            asc_num += 1
    # desc
    desc_num = 0
    target = N
    for P_i in reversed(P):
        if P_i == target:
            target -= 1
            desc_num += 1
    print(min(N-asc_num, N-desc_num))



if __name__ == '__main__':
    solve()