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: Accepted

Solution code:

N = int(input())
B= [0] * N

for i in range(0, N):
	bb = int(input())
	B[bb-1] = i

m = 1
mx = 1
for i in range(1, N):
	if B[i] > B[i-1]:
		m = m + 1
		mx = max(mx, m)
	else:
		m = 1

print(N - mx)

Submission status: Accepted

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

maxSet = 0

temp = 1
i = 2
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: Accepted

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, 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 n != 0 and 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: Accepted

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):
		#print(out)
		if ps[i+1] >= ps[i]:
			cnt += 1
		else:
			out = max(cnt, out)
			cnt = 1
	else:
		if out == 0:
			out = n 
		else:
			out = max(cnt, out)

	print(n - out)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

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

a = 0
for i in range(N):
	a = max(a, cnt[i+1])
print(N - a)

Submission status: Accepted

Solution code:
import sys;raw_input = sys.stdin.readline
N = int(raw_input())
P = [None]*N
for i in xrange(N):
    P[i] = int(raw_input())-1
def solve(C):
    N = len(C)
    I = [None]*N
    for i in xrange(N):
        I[C[i]] = i
    D = [1]*N 
    for i in xrange(1, N):
        D[i] = (D[i-1] + 1) if I[i] > I[i-1] else 1
    return N - max(D)
print solve(P)

Submission status: Accepted

Solution code:
N = int(input())

L = {}
for i in range(N):
    n = int(input())
    if n-1 in L:
        L[n] = L.pop(n-1)
        L[n] += 1
    else:
        L[n] = 1
    
ans = N
for k,v in L.items():
    if N-v < ans:
        ans = N-v
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
dp=[0 for _ in range(N+1)]

for i in range(N):
  x=int(input())
  dp[x]=dp[x-1]+1

print(N-max(dp))

Submission status: Accepted

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

# ans = N - (1,2,3 のように連続する最長の部分列(飛ばしてOK)の長さ)

memo = {}
for p in P:
  if p-1 in memo:
    memo[p] = memo[p-1] + 1
  else:
    memo[p] = 1

print(N - max(memo.values()))

Submission status: Accepted

Solution code:
def solve(N, P):
    xs = [0] * N
    for i, x in enumerate(P):
        xs[x - 1] = i
    r = 0
    c = 0
    p = -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: Accepted

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
longest = max(longest, seq)
print(N - longest)

Submission status: Accepted

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

n = int(raw_input())

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

count = np.zeros([n+1],int)

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

#print count

#print count

#print np.max(count)

ans = n-np.max(count)

print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N = int(input())
cache = dict()
for i in range(1, N+1):
    p = int(input())
    cache[p] = cache.get(p-1, 0) + 1
print(N-max(cache.values()))

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

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

pos = [0 for _ in range(n+1)]

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

longest = 1
current = 1

for q in range(1, n + 1 - 1):
    if pos[q] < pos[q + 1]:
        current += 1
    else:
        if current > longest:
            longest = current
        current = 1

if current > longest:
    longest = current

print(n - longest)

Submission status: Accepted

Solution code:
n = int(input())
dic = {}
for i in range(n):
  p = int(input())
  if p - 1 in dic:
    dic[p] = dic[p - 1] + 1
  else:
    dic[p] = 1
Max = 0
for i in range(1, n + 1):
  di = dic[i]
  if di > Max:
    Max = di

print(n - Max)

Submission status: Accepted

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 and dd[pre + 1] > s:
            i = dd[pre + 1]
            if xx[i] >= 0:
                xx[s] = xx[i] + count
                break
            pre += 1
            count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
import itertools


def read():
    return int(input())


def readmap():
    return map(int, input().split())


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


N = read()
P = []
for _ in range(N):
    P.append(read())

dic = {}
for p in P:
    if p in dic.keys():
        dic[p+1] = dic[p] + 1
        del dic[p]
    else:
        dic[p+1] = 1

print(N - max(dic.values()))

Submission status: Accepted

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

W = {}
for p in P:
    if p in W.keys():
        W[p+1] = W[p] + 1
        del W[p]
    else:
        W[p+1] = 1

#print(W)
print(N - max(W.values()))

Submission status: Accepted

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


def main():
    N = int(input())
    P = [int(input()) - 1 for i in range(N)]
    counter = [0 for i in range(N + 1)]

    max_ = 0
    for p in P:
        counter[p] = counter[p - 1] + 1
        if max_ < counter[p]:
            max_ = counter[p]

    print(N - max_)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
pos = [-1 for i in range(n + 1)]
best = [1 for i in range(n)]
for i in range(n):
    pos[p[i]] = i
for i in range(n):
    if p[i] == 1:
        continue
    j = pos[p[i] - 1]
    if j < i:
        best[i] = best[j] + 1
print(n - max(best))

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7


def solve(f):
    n = f.read_int()
    a = [0] * (n+1)
    for i in xrange(n):
        a[f.read_int()] = i+1

    ma = 0
    cur = 0
    st = 1
    for i in xrange(1,n+1):
        if cur > a[i]:
            ma = max(ma, i-st)
            st = i
        cur = a[i]
    ma = max(ma, n+1-st)

    return n-ma


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    a = map(int, stdin.read().split(), repeat(10, n))
    p = [0] * n
    for i, x in enumerate(a):
        p[x-1] = i
    x = ans = 1
    for i in xrange(1, n):
        if p[i] > p[i-1]:
            x += 1
        else:
            x = 1
        if ans < x:
            ans = x
    print n - ans
main()

Submission status: Accepted

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
x,r,num,ans = [0 for i in range(n)],0,1,0
for i in range(n): x[p[i]-1] = i
while r!=n-1:
	r += 1
	if x[r-1]<x[r]: num = num+1
	else: ans,num = max(ans,num),1
ans = max(ans,num)
print(n-ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()

inv = [0] * N
for i in range(N):
  x = read()
  inv[x-1] = i

inv.append(-1)
print(inv, file=stderr)

maxans = 1
count = 1
for i in range(1, N+1):
  if inv[i-1] < inv[i]:
    count += 1
  else:
    print('stopped at ' + str(i), file=stderr)
    maxans = max(maxans, count)
    count = 1

print(maxans, file=stderr)
print(N - maxans)

Submission status: Accepted

Solution code:
n = int(input())
t = [0]*n
for i in range(n):
    p = int(input())-1
    t[p] = i
l = 1
m = 1
for i in range(n-1):
    if t[i] < t[i+1]:
        l += 1
    else:
        if m < l:
            m = l
        l = 1
if m < l:
    m = l
print(n-m)

Submission status: Accepted

Solution code:
exec("def nWord(): nWord.cache = raw_input() if not hasattr(nWord, 'cache') or nWord.cache=='' else nWord.cache ; pos = nWord.cache.find(nWord.sep) ; ret, nWord.cache = (nWord.cache, '') if pos==-1 else (nWord.cache[:pos], nWord.cache[pos+1:].lstrip(nWord.sep)) ; return ret") ; exec("nWord.sep = ' '") ; exec("def ___nLine2(): ret, nWord.cache = (raw_input(), nWord.cache if hasattr(nWord, 'cache') else '') if not hasattr(nWord, 'cache') or nWord.cache=='' else (nWord.cache, '') ; return ret") ; exec('def nInt(): return int(nWord())') ; exec('def nFloat(): return float(nWord())') ; exec("def ___nAuto2():\n ret = nWord()\n try: return int(ret)\n except: pass\n try: return float(ret)\n except: return ret") ; exec("def nAuto(n=None): return ___nAuto2() if n is None else [___nAuto2() for i in range(n)]") ; exec("def nLine(n=None): return ___nLine2() if n is None else [___nLine2() for i in range(n)]")

import itertools

P = nAuto(nAuto())

P2 = [-1]*len(P)
for i, p in enumerate(P):
    P2[p-1] = i

n = 0
mn = 0
bp = len(P)+100
for p in P2:
    assert 0<=p
    if p<bp:
        n = 0
    bp = p
    n += 1
    mn = max(mn, n)

print(len(P) - mn)

Submission status: Accepted

Solution code:
N = input()
P = [input() for _ in range(N)]
T = [0]*(N+1)
for p in P:
  T[p] = T[p-1]+1
print N-max(T)

Submission status: Accepted

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

tmp_f = {}
for p in ppp:
    if p - 1 in tmp_f:
        tmp_f[p] = tmp_f[p - 1] + 1
    else:
        tmp_f[p] = 1

# tmp_b = {}
# for p in ppp[::-1]:
#     if p + 1 in tmp_b:
#         tmp_b[p] = tmp_b[p + 1] + 1
#     else:
#         tmp_b[p] = 1

cnt = max(tmp_f.values())
print(n - cnt)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# B
N = int(input())
P_list = []
Q_list = [0]*(N+1)
for i in range(1, N+1):
    p = int(input())
    Q_list[p] = i
    
straight = 1
max_straight = 1
for i in range(1, N):
    if Q_list[i] < Q_list[i+1]:
        straight += 1
        max_straight = max(straight, max_straight)
    else:
        straight = 1
        
print(N - max_straight)

Submission status: Accepted

Solution code:

# find the longest subsequence where the common difference is 1

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

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

got=[0]*(n+1)
for i in p:
    got[i]=got[i-1]+1

print(n-max(got))

Submission status: Runtime Error

Solution code:
n=int(input())

ans=[0 for _ in range(n) ]

for i in range(n):
  a=int(input())
  ans[a-1]+=(i+1)
  
ch=1

ans1=[]
  
for x in range(n-1):
  if ans[x]<ans[x+1]:
    ch+=1
    
  else:
    ans1.append(ch)
    ch=1
  
    
print(n-max(ans1))

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    p = []
    for _ in range(n):
        p.append(int(input()))
    ans = 0
    add = []
    for i in range(n//2+1):
        if p[i] > n//2:
            ans += 1
            add.append(p[i])
            p[i] = 0
    p += sorted(add)
    P = []
    for p_ in p:
        if p_>0:
            P.append(p_)
    B = P[0:n//2]
    P = P[n//2:]
    m = B[0]
    c = 0
    for i in range(len(B)):
        if B[i]>m:
            m = B[i]
        elif B[i]<m:
            if B[i]>c:
                c = B[i]
    ans += c
    m = P[-1]
    c = 0
    for i in range(len(P)):
        if P[-1-i]<m:
            m = P[-1-i]
        elif P[-1-i]>m:
            if n-P[-1-i]+1>c:
                c = n-P[-1-i]+1
    ans += c
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
P, Q = [], [0]*(N+1)
for i in range(1,N+1):
    p = int(input())
    P.append(p)
    Q[p] = i
cnt = 1
res = []
for i in range(1,N):
    if Q[i] < Q[i+1]:
        cnt += 1
    else:
        res.append(cnt)
        cnt = 1
print(N-max(res))

Submission status: Runtime Error

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

cnt = 0
if P[0] == 1:
    isFirstNum = 1
else:
    isFirstNum = 0
    cnt +=1

if P[-1] == N:
    isLastNum = 1
else:
    isLastNum = 0
    cnt +=1
    
isBefore = 0
isAfter = 0

P.remove(1)
P.remove(N)


for i in range(len(P)-1):
    if P[i]>P[i+1]:
        cnt += 1
        if N-P[i]<=P[i+1]-1:
            isAfter = 1
        else:
            isBefore = 1

ope = cnt+isBefore*isFirstNum+isAfter*isLastNum

print(ope)

Submission status: Runtime Error

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

cnt = 0
if P[0] == 1:
    isFirstNum = 1
else:
    isFirstNum = 0
    cnt +=1

if P[-1] == N:
    isLastNum = 1
else:
    isLastNum = 0
    cnt +=1
    
isBefore = 0
isAfter = 0

P.remove(1)
P.remove(N)


for i in range(len(P)-1):
    if P[i]>P[i+1]:
        cnt += 1
        if P[i]>N//2:
            isAfter = 1
        else:
            isBefore = 1

ope = cnt+isBefore*isFirstNum+isAfter*isLastNum

print(ope)

Submission status: Runtime Error

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

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

print(q - max(q))

Submission status: Runtime Error

Solution code:
n=int(input())
f,s=n//2,n//2+1
p=[int(input()) for _ in range(n)]
fi=p.index(f)
si=p.index(s)
ans=0
if fi>si:
    ans+=1
for i in range(fi-1,-1,-1):
    if p[i]==f-1: f-=1
for i in range(si+1,n):
    if p[i]==s+1: s+=1
ans+=f-1+n-s
print(f-1+n-s)

Submission status: Runtime Error

Solution code:
#pdf見た
n = int(input())
q = [0]*n
for i in range(n):
    p = int(input())-1
    q[p] = i
    
s=f=0
c = set()
for i in range(2,n):
    if q[i]<q[i-1]:
        f=i-1
        c.add(f-s+1)
        s=i
print(n-max(c))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
dbg = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

N = ini()
P = list(map(int, sys.stdin.readlines()))
INF = 1 << 40


def solve():
    inds = [None] * (N + 1)
    for i, x in enumerate(P):
        inds[x] = i

    streak = [1] * (N + 1)
    for k in range(2, N + 1):
        if inds[k - 1] < inds[k]:
            streak[k] = streak[k - 1] + 1
    ans = INF
    for k in range(2, N + 1):
        r = 0 if k == P[-1] else 1
        r += N - k
        l = (k - 1) - streak[k - 1]
        if ans > l + r:
            ans = l + r
        # dbg(f"{ans=} {l=} {r=}")
    return ans


print(solve())

Submission status: Runtime Error

Solution code:
N = int(input())
dic = {}
nums = []
for i in range(N):
    num = int(input())
    dic[num] = i+1
    nums.append(num)
ans = 0
for i in range(N):
    if nums[i] <= nums[-1]:
        break
#ans += i
base = nums[i]
print(base)
init_num = base
# baseの位置 > base+1の所できる.
move = 0
while base <= nums[-1]:
    old_i = i
    i = dic[base + 1]
    if old_i > i:
        break
    base += 1
    move += 1
#import IPython;IPython.embed()
#if base != nums[-1]:
#    ans += 1
ans += init_num - 1
ans += N - base
#ans += N - nums[-1]
print(ans)


"""
戦略的には
1. a_0 > a_nの時,どちらかをずらす.
a_nを前に持っていくか,a_0を後ろに持っていくか...
どっちでも変わらない.
"""

Submission status: Runtime Error

Solution code:
n=int(input())
p=[int(input()) for _ in range(n)]
dp=[0]*(n+10)
for i in p:
  dp[p]=dp[p-1]+1
print(n-max(dp))

Submission status: Runtime Error

Solution code:
#N, *a = map(int, open(0).read().split())
def main():
    N = int(input())
    a=[]
    for i in range(N):
        a.append(int(input()))

    b = [0 for _ in range(N+1)]
    cnt = 1
    ans = 0
    flag = 1
    i = 0
    for i in reversed(range(N)):
        if b[a[i]+1] > 0:
            b[a[i]] = b[a[i]+1] + 1
        else:
            b[a[i]] = 1
        
    return N-max(b)
print(main())

Submission status: Runtime Error

Solution code:

N=int(input())
data=[int(input()) for i in range(N)]
mae=N//2+N%2
count=0
print(N-[i for i in data if i>N//2+N%2][0]+[i for i in data if i<=N//2+N%2][0])

Submission status: Runtime Error

Solution code:
N = int(input())
P = []
for i in range(N):
    p = int(input())
    P.append(p)
x = P[0] - 1
y = N - P[N-1]
ansx = x
ansy = y
import copy
X = copy.deepcopy(P)
Y = copy.deepcopy(P)
for i in range(1,x+1):
    X.remove(i)
for j in range(y,N+1):
    Y.remove(i)
while min(X) == X[0]:
    X.pop(0)
while max(Y) == Y[len(Y)-1]:
    Y.pop()
p = X.pop()
q = Y.pop(0)
ansx += N - p
ansy += q - 1
ans = min(ansx,ansy)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
P = []
for i in range(n):
    p = int(input())
    P.append(p)
x = P[0] - 1
y = N - P[N-1]
ansx = x
ansy = y
import copy
X = copy.deepcopy(P)
Y = copy.deepcopy(P)
for i in range(1,x+1):
    X.remove(i)
for j in range(y,N+1):
    Y.remove(i)
while min(X) == X[0]:
    X.pop(0)
while max(Y) == Y[len(Y)-1]:
    Y.pop()
p = X.pop()
q = Y.pop(0)
ansx += N - p
ansy += q - 1
ans = min(ansx,ansy)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
memo = [0 for i in range(n)]
for i in range(n):
  memo[int(input())-1] = i
cand = 0
tmp = 0
for n1, n2 in range(n - 1):
  if n2 > n1:
    tmp += 1
    if tmp > cand:
      cand = tmp
  else:
    tmp = 0
print(n - cand - 1)

Submission status: Runtime Error

Solution code:
N = int(input())
P = [0] * N

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

sorted_P = sorted(P)

max_i = P.index(N)
j = 1
for i in range(max_i, -1, -1):
    if P[i] == sorted_P[N - 1 - j]:
        j += 1

min_i = P.index(1)
k = 1
for i in range(min_i, N):
    if P[i] == sorted_P[k]:
        k += 1
ans = N - max(j, k)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
P = [0] * N

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

sorted_P = sorted(P)

max_i = P.index(N)
j = -2
for i in range(max_i, -1, -1):
    if P[i] == sorted_P[j]:
        j -= 1

min_i = P.index(1)
k = 1
for i in range(min_i, N):
    if P[i] == sorted_P[k]:
        k += 1
ans = N - max((-j-1), k)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
P = [0] * N

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

sorted_P = sorted(P)
sorted_rev_P = list(reversed(sorted_P))

max_i = P.index(sorted_P[-1])
j = 1
for i in range(max_i, -1, -1):
    if P[i] == sorted_rev_P[j]:
        j += 1
min_i = P.index(1)
k = 1
for i in range(min_i, N):
    if P[i] == sorted_P[k]:
        k += 1
ans = N - max(j, k)
print(ans)

Submission status: Runtime Error

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

T = [1] * N
L = []
for i in P:
  for j in L:
    if T[j] + j == i:
      T[j] += 1
      break
  else:
    L.append(i)

print(N - max(T))

Submission status: Runtime Error

Solution code:
# This Python 3 environment comes with many helpful analytics libraries installed
# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python
# For example, here's several helpful packages to load in 

import numpy as np # linear algebra
import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)

# Input data files are available in the "../input/" directory.
# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory

import os
#print(os.listdir("../input"))

import sys
#def input():
#    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
'''
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
'''

test_data1 = '''\
8
6
3
1
2
7
4
8
5
'''

test_data2 = '''\
6
3
2
5
1
4
6
'''

test_data3 = '''\
4
1
3
2
4
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        #print(f.readlines())
        #print(f.read())
        # Start Input code ---------------------------------------
        n=int(f.readline())
        p=[0]*n
        for i in range(n):
            p[i]=int(f.readline())
        # End Input code ---------------------------------------
else:
    n=int(input())
    p=[0]*n
    for i in range(n):
        p[i]=int(input())
    # End Input code ---------------------------------------

a=[0]*n
cnt=1
ans=0
for i in range(n):
    a[p[i]-1]=i
#print('n,p=',n,p,a)
for i in range(n):
    if i==0:
        pre=a[0]
    else:
        if a[i]>pre:
            cnt+=1
        else:
            ans=max(ans,cnt)
            cnt=1
    ans=max(ans,cnt)
    pre=a[i]
print(n-ans)

Submission status: Runtime Error

Solution code:
# This Python 3 environment comes with many helpful analytics libraries installed
# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python
# For example, here's several helpful packages to load in 

import numpy as np # linear algebra
import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)

# Input data files are available in the "../input/" directory.
# For example, running this (by clicking run or pressing Shift+Enter) will list the files in the input directory

import os
#print(os.listdir("../input"))

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
'''
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
'''

test_data1 = '''\
8
6
3
1
2
7
4
8
5
'''

test_data2 = '''\
6
3
2
5
1
4
6
'''

test_data3 = '''\
4
1
3
2
4
'''
td_num=3

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3
    
if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        #print(f.readlines())
        #print(f.read())
        # Start Input code ---------------------------------------
        n=int(f.readline())
        p=[0]*n
        for i in range(n):
            p[i]=int(f.readline())
        # End Input code ---------------------------------------
else:
    n=int(input())
    p=[0]*n
    for i in range(n):
        p[i]=int(input())
    # End Input code ---------------------------------------

a=[0]*n
cnt=1
ans=0
for i in range(n):
    a[p[i]-1]=i
#print('n,p=',n,p,a)
for i in range(n):
    if i==0:
        pre=a[0]
    else:
        if a[i]>pre:
            cnt+=1
        else:
            ans=max(ans,cnt)
            cnt=1
    pre=a[i]
print(n-ans)

Submission status: Runtime Error

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]+1] = chain[a[i]]+1
print(max(chain))

Submission status: Runtime Error

Solution code:
N = int(input())
a = [0 for i in range(N)]
chain = [0 for i in range(N)]
for i in range(N):
  a[i] = int(input())
  chain[a[i]] = chain[a[i]-1]+1
print(max(chain))

Submission status: Runtime Error

Solution code:
n = int(raw_input())
a = {}

for i in range(1, n+1):
    r = int(raw_input())
    a[r] = i


def asc(i):
    if a[i] < a[i+1]:
        return asc(i+1)
    else:
        return i

def desc(i):
    if a[i] < a[i-1]:
        return i-1
    else:
        return desc(i-1)

print min(n-asc(1),desc(n))

Submission status: Runtime Error

Solution code:
N = int(input())
list = {0:0}
for i in range(1,N):
    list[int(input())] = i
x = 0
for j in range(2,N-1):
    if list[j-1] > list[j] :
     x = x + 1
print(x)

Submission status: Runtime Error

Solution code:
N = int(input())
dictional = {0:0}
for i in range(1,N):
  dictional[int(input())] = i
  
x = 0
for j in range(2,N-1):
  if dictional[j-1] > dictional[j] :
    x = x + 1
print(x)

Submission status: Runtime Error

Solution code:
N = int(input())
dictional = {}
for i in range(1,N):
  dictional[int(input())] = i
  
x = 0
for j in range(2,N-1):
  if dictional[j-1] > dictional[j] :
    x = x + 1
print(x)

Submission status: Runtime Error

Solution code:
import numpy as np



def ii():
    return int(input())




def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l



N = ii()

P = lvi(N)

'''
P = []
for _ in range(N):
    p = ii()
    P.append(p -1)

print(P)
'''

#fill( Q, Q + N, 0)
Q = [0 for i in range(N)]


#print( 'Q', Q)

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


maxcnt = 1
cnt = 1

print( 'Q', Q)

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

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

Submission status: Runtime Error

Solution code:
in = raw_input().split()
N = in[0]
P = in[1:]

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

Solution code:
import sys

n = int(str(sys.stdin.readline()))
p = [int(str(sys.readline())) for i in range(0, n)]


x = 0

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

print(x)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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