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: Runtime Error

Solution code:
from itertools import count
n = int(input())
l = [ int(input()) for i in range(n)]
ans = tuple(sorted(l))

checked = set()

s = [(l, 0)]
for loop_count in count():
    #print(s, checked)
    tl, ns = s.pop(0)
    #print(loop_count, ns, len(s), len(checked))
    if tuple(tl) in checked:
        continue
    if ans == tuple(tl):
        print(ns)
        break
    for i in range(n):
        n1 = list(tl)
        if i != n - 1 and i != 0 and n1[i] != n1[i-1] + 1:
            c = n1.pop(i)
            n1.append(c)
            if(tuple(n1) not in checked):
                s.append((n1, ns+1))
        n2 = list(tl)
        if i != 0 and i != n - 1 and n2[i] + 1 != n2[i+1]:
            c = n2.pop(i)
            n2.insert(0, c)
            if(tuple(n2) not in checked):
                s.append((n2, ns+1))
    checked.add(tuple(tl))

Submission status: Runtime Error

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
seq = []
for i in range(N-1):
    if q[i+1] - q[i] > 0:
        cnt += 1
    else:
        seq.append(cnt)
        cnt = 1
max_cnt = max(seq)
print(N - max_cnt)

Submission status: Runtime Error

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] * N
for i in range(N):
    q[p[i]-1] = i

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: Runtime Error

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

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

Submission status: Runtime Error

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: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

candidate = []
num = 0
for i in range(N-2):
    num += 1
    if Q[i] > Q[i+1]:
        candidate.append(num)
        num = 0
    if i == N-2:
        candidate.append(num)
print(N - max(candidate))

Submission status: Runtime Error

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
while n-1>j:
  if q[i+1]-q[i]>0:
     k+=1
  else:
     s=max(s,k)
     k=1
  j+=1
s=max(s,k)
print(n-s)

Submission status: Runtime Error

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

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

print(n - max(tmp))

Submission status: Runtime Error

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

P = list(map(int,P))

ans = 0
if N == 1:
    print(1)
    sys.exti()
err = [1]
P_lft = []
P_rgh = []
while len(err) > 0:
#    print(P)
    del err
    err = []
    del P_lft

    P_lft = P[:N//2]

    for i in P_lft:
        if i > N//2:
            err.append(i)
            P.remove(i)

    ans = ans + len(err)

    err.sort()
    P = P + err


P_lft = P[:N//2]
tmp = [int(i+1) for i in range(N//2)]

while tmp != P_lft:
    ans = ans + 1
    if P_lft[0] != 1:
        P_lft.remove(P_lft[0]-1)
        P_lft.insert(0,P_lft[0]-1)
    else:
        P_lft.remove(N//2)
        P_lft.insert(0,N//2)

del P_lft
P_lft = P[N//2:]
tmp =[]
tmp = [int(i+N//2+1) for i in range(N//2)]

while tmp != P_lft:

    ans = ans + 1
    if P_lft[-1] != N:
        P_lft.remove(P_lft[-1]+1)
        P_lft.append(P_lft[-1]+1)
    else:
        P_lft.remove(N//2+1)
        P_lft.append(P_lft[-1]+1)

print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(input())for _ in[0]*n]
if n%2==0:
    m1=n//2
    m2=m1+1
    m1i=a.index(m1)
    m2i=a.index(m2)
    a1=[a[i] for i in range(m1i) if a[i]<m1]
    a2=[a[i] for i in range(m1i+1,n) if a[i]<m1]
    al=sorted(a2)+a1
    a3=[a[i] for i in range(m2i) if a[i]>m2]
    a4=[a[i] for i in range(m2i+1,n) if a[i]>m2]
    ar=a4+sorted(a3)
    r=len(a2)+len(a3)
    l=al.index(m1-1)
    r+=m1-2-l
    r+=ar.index(m2+1)
else:
    m=n//2+1
    mi=a.index(m)
    a1=[a[i] for i in range(mi) if a[i]<m]
    a2=[a[i] for i in range(mi+1,n) if a[i]<m]
    al=sorted(a2)+a1
    a3=[a[i] for i in range(mi) if a[i]>m]
    a4=[a[i] for i in range(mi+1,n) if a[i]>m]
    ar=a4+sorted(a3)
    r=len(a2)+len(a3)
    l=al.index(m-1)
    r+=m-2-l
    r+=ar.index(m+1)
print(r)

Submission status: Runtime Error

Solution code:
N = int(input())
a = [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: Runtime Error

Solution code:
N = int(input())
a = [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: Runtime Error

Solution code:

from bisect import bisect

n = int(input())
p = [int(input()) for _ in range(n)]
lsi = []
max = 0
lsi.append(p[0])

for i in range(1,n):
    tmp = 0
    num = p[i]
    bisect(lsi, num)
    doko = lsi.index(num)

    for j in range(1,num):
        if num - j == lsi[doko - j]:
            tmp += 1
        else:
            break
    if tmp > max:
        max = tmp

print(n -1 - max)

Submission status: Runtime Error

Solution code:
import numpy as np

N = input()
a = [input() for i in range(N)]
print (a)

for i in range( N/2 -1 ,0):

    if np.where(i) > np.where(i + 1):
        a.insert(0, i)
        a.pop(i + 1)
        cnt+1


for i in range( N/2, N):

    if np.where(i) > np.where(i + 1):
        a.insert( N, i)
        a.pop(i)
        cnt+1



print(cnt)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
P = []
for i in range(N):
    P.append(int(input()))
index = []
for i in range(N):
    index.append(P.index(i + 1))
count = []
temp = 1
for i in range(N - 1):
    if index[i] < index[i + 1]:
        temp += 1
    else:
        count.append(temp)
        temp = 1
print(N - max(count))

Submission status: Runtime Error

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 i == dellist[j] + key:
        j += 1
        l -= 1
    elif P[i] != l:
        cnt += 1
    l += 1
print(len(addlist) + int(cnt / 2))

Submission status: Runtime Error

Solution code:
N = int(input())
a = [int(input()) for i in range(N)]
c = 0
dai = a.index(2)
for i in range (1,N):
  ti = a.index(i)
  dai = a.index(i+1)
  if  ti <  dai:
      c += 1
  else:
     break
d = 0
for  i  in range (N,1,-1):
  dai  =  a.index(i)
  ti =  a.index(i-1)
  if   ti < dai:
    d += 1
  else:
    break
jo =  max(c,d)
ans = N - jo - 1
print(ans)

Submission status: Runtime Error

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 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: Runtime Error

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:][::-1]:
        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 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: Runtime Error

Solution code:
N = int(input())

l = list(range(N))

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

# print(l)

count_l = []
count = 1

st_ind = l.index(1)
num = 2

while num <= N:
    next_ind = l.index(num)
    if st_ind < next_ind:
        count += 1
    else:
        count_l.append(count)
        count = 1

    st_ind = next_ind
    num += 1

print(N - max(count_l))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
p = [ int(input()) for i in range(n)]
pmin = -1
pmax = n
for i,j in enumerate(p):
    if i + 1 == j:
        continue
    else:
        pmin = i
        break
for i,j in enumerate(p[::-1]):
    if n - i  == j:
        continue
    else:
        pmax = n - i -1
        break


nppma  = np.array(p[:pmax + 1 ],dtype="int32")
nppmi = np.array(p[pmin  :],dtype="int32")
#print(nppmi)
#print(nppma)
nmax = nppma.argmax()
nmin = nppmi.argmin()
#print(nppmi[:nmin])
#print(nppma[nmax +1:])
ansmin =  n  + 1 - np.min(nppmi[:nmin])
ansmax = np.max(nppma[nmax + 1:])
print(min(ansmin,ansmax))

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
p = [int(input()) for _ in range(n)]
ans = 0
for i in range(n):
    maxi = p.index(max(p))
    mini = p.index(min(p))
    length = len(p)
    maxi_len = length-maxi-1
    if maxi_len == 0 and mini == 0:
        p2 = p.copy()
        p2.pop(0)
        p2.pop(-1)
        for k in range(n):
            maxi2 = p2.index(max(p2))
            mini2 = p2.index(min(p2))
            length2 = len(p2)
            maxi_len2 = length2 - maxi2 - 1
            if length2 <= 1:
                print(ans)
                sys.exit()
            if maxi_len2 == 0 and mini2 == 0:
                p2.pop(0)
                p2.pop(-1)
                continue
            if maxi_len2 > mini2:
                val = max(p2)
                p.pop(p.index(val))
                p.insert(-1,val)
                ans += 1
                break
            else:
                val = min(p2)
                p.pop(p.index(val))
                p.insert(0, val)
                ans += 1
                break
    if maxi_len > mini:
        p.pop(maxi)
    else:
        p.pop(mini)
    ans += 1
print(ans)

Submission status: Runtime Error

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

import os
import sys
import math
import numpy as np


def calc_left(var, 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

    # ans += var - 1
    return var - 1


def calc_right(var, 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


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 arr.index(border) > arr.index(border + 1):
        cost_left = calc_left(border, arr_left)
        cost_right = calc_right(border + 1, 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(border, arr_left)
    ans += calc_right(border + 1, arr_right)


    print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

ZOUKA=[0]*(N)
JUDGE=list(range(1,N+1))

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

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

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

Submission status: Runtime Error

Solution code:
def main():
    N=int(input())
    P=[0]*N
    p=[False]*(N+1)
    P[0]=int(input())
    for i in range(N-1):
        P[i+1=int(input())
        if P[-1]-1 in P[:-1]:
            p[P[-1]-1] = True
    ans=0
    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: Runtime Error

Solution code:
n = int(input())
p = []
for i in range(n):
  p.append(int(input()))
for i in range(1, n):
  if p.index(i) > p.index(i + 1):
    upper = n - i
    break
for i in range(n, 1, -1):
  if p.index(i) < p.index(i - 1):
    under = i - 1
    break
print(min(upper, under))

Submission status: Runtime Error

Solution code:
#include<stdio.h>
int a[200005];
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n; i++)scanf("%d",&a[i]);
int ans = n;
int cur = n;
for(i=n;i>=1;i--)
if(a[i]==ans)ans--;
printf("%d\n",ans);
return 0;
}a

Submission status: Runtime Error

Solution code:
a,b,c,k = map(int, input().split())
if k%2==0: print(a-b)
else: print(b-a)