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: Time Limit Exceeded

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


def iffront(i):
    return not ps[i]-1 in ps[:i]

def ifback(i):
    return not ps[i]+1 in ps[i+1:]

fsinds = filter(iffront,range(n))
bsinds = list(filter(ifback,range(n)))


anspre = 0
anstmp =0
pb=0


for i in fsinds:
    #print ('i',i)
    #print ('p',ps[i])
    pp = ps[i]
    pbs = [ps[j] for j in bsinds if ps[j] >= pp]
    #print('pbs',pbs)
    if pbs == []:
        anstmp = 0
    else:
        anstmp = min(pbs) - ps[i]
        #print('pf',min(pbs))
    if anstmp > anspre: anspre = anstmp

print (n-1-anspre)

Submission status: Time Limit Exceeded

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

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

ZOUKA=[0]*(N+1)

for i in range(1,N+1):
    if ZOUKA[i]==-1:
        continue
    
    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:
            ZOUKA[r]=-1
            r+=1
            ZOUKA[i]+=1

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

Submission status: Time Limit Exceeded

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

    # asc
    asc_num = 0
    target = 1
    _dict = {}
    for P_i in P:
        del_flag = False
        if P_i not in _dict.keys() and P_i not in _dict.values():
            _dict[P_i] = P_i + 1
        for k, v in _dict.items():
            if v == P_i:
                _dict[k] = P_i + 1 
            elif k-1 == P_i:
                asc_num = max(asc_num, v-k)
        if del_flag:
            del _dict[k]
    for k, v in _dict.items():
        asc_num = max(asc_num, v-k)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = []
lis = []
for i in range(n):
	a = int(input())
	lis.append(a)
	li.append(a)
co = 0
cou = 0
for i in range(n-1):
	if lis.index(n-(i+1)) > lis.index(n-i):
		lis.remove(n-(i+1))
		lis.insert(0,n-(i+1))
		co += 1

for k in range(n-1):
	if li.index(k+2) < li.index(k+1):
		li.remove(k+2)
		li.append(k+2)
		cou += 1
print(min(co,cou))

Submission status: Time Limit Exceeded

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

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

ZOUKA=[0]*(N+1)

for i in range(1,N+1):
    if ZOUKA[i]==-1:
        continue
    
    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:
            ZOUKA[r]=-1
            r+=1
            ZOUKA[i]+=1

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
P = []

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

Ps = sorted(P)

ans = 0
for i in range(n,0,-1):
    if not(P.index(i)==0): 
        if max(P[0:P.index(i)]) > i:
            ans += 1
            P.remove(i)
            P.insert(0,i)
    if P == Ps: break

print(ans)

Submission status: Time Limit Exceeded

Solution code:


n = int(input())
ps = [int(input()) for i in range(n)]


def iffront(i):
    return not ps[i]-1 in ps[:i]

def ifback(i):
    return not ps[i]+1 in ps[i+1:]

fsinds = filter(iffront,range(n))
bsinds = list(filter(ifback,range(n)))


anspre = 0
anstmp =0
pb=0


for i in fsinds:
    #print ('i',i)
    #print ('p',ps[i])
    pp = ps[i]
    pbs = [ps[j] for j in bsinds if ps[j] >= pp]
    #print('pbs',pbs)
    if pbs == []:
        anstmp = 0
    else:
        anstmp = min(pbs) - ps[i]
        #print('pf',min(pbs))
    if anstmp > anspre: anspre = anstmp

print (n-1-anspre)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [int(input()) for i in range(n)]
asc = 0
desc = 0
for t in range(1, n+1):
    target = t
    tmp = 0
    for i in p:
        if i == target:
            tmp += 1
            target += 1
    asc = max(asc, tmp)
for t in range(n, 0, -1):
    target = t
    tmp = 0
    for i in reversed(p):
        if i == target:
            tmp += 1
            target -= 1
    desc = max(desc, tmp)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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


# すでに並んでる列
ordered = []
unordered = []

previous = 0
for i in p:
    if previous < i:
        ordered.append(i)
        previous = i
    else:
        unordered.append(i)
        

count = 0

loopc = len(unordered)
for _ in range(loopc):

    center = ordered[len(ordered)//2]

    # センターに近いものを選択
    t = min(unordered, key=(lambda x: abs(x - center)))

    count += 1
    index = 0
    if center > t:
        index = 0
        for i in ordered:
            if i < t:
                count +=1
                index +=1
            else:
                break
    else:
        index = -1
        for i in reversed(ordered):
            if i > t:
                count +=1
                index -=1
            else:
                break


    unordered.remove(t)
    ordered.insert(index, t)

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

M = []
P = []
for p in L:
    try:
        s = M.index(p-1)
    except:
        M.append(p)
        P.append(1)
        continue
    M[s] = p
    P[s] += 1

print(N-max(P))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
# x = [[1, 2, 4, 3], [2, 4, 1, 3], [2, 4, 3, 1], [4, 2, 1, 3], [4, 3, 2, 1]]
lens = []
for i in p:
    if i-1 not in lens:
        lens.append(i)
    else:
        lens[lens.index(i-1)] += 1
lens.sort()
x = 0
temp = 0
for i in lens:
    x = max(i-temp, x)
    temp = i
print(n-x)

Submission status: Time Limit Exceeded

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

    # asc
    asc_num = 0
    target = 1
    _dict = {}
    for P_i in P:
        del_flag = False
        if P_i not in _dict.keys() and P_i not in _dict.values():
            _dict[P_i] = P_i + 1
        for k, v in _dict.items():
            if v == P_i:
                _dict[k] = P_i + 1 
    for k, v in _dict.items():
        asc_num = max(asc_num, v-k)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


lsi = list(0 for _ in range(n+1))
group = []

for i in range(n):
    num = p[i]
    find = False

    for group_i in group:
        if num - 1 in group_i:
            group_i.add(num)
            find = True

    if find:
        continue
    else:
        tmp = set()
        tmp.add(num)
        group.append(tmp)

max_len = 0
for group_i in group:
    if max_len < len(group_i):
        max_len = len(group_i)

print(n - max_len)

Submission status: Time Limit Exceeded

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

max_count = 1
for i in range(n):
    count = 1
    target = p[i] + 1
    for j in range(i + 1, n):
        if p[j] == target:
            count += 1
            target += 1
    if max_count<count:
        max_count=count
print(n-max_count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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


# すでに並んでる列
ordered = []
unordered = []

previous = 0
for i in p:
    if previous < i:
        ordered.append(i)
        previous = i
    else:
        unordered.append(i)
        

count = 0

loopc = len(unordered)
for _ in range(loopc):

    center = ordered[len(ordered)//2]

    # センターに近いものを選択
    t = min(unordered, key=(lambda x: abs(x - center)))


    count += 1
    if center > t:
        for i in ordered:
            if i < t:
                count +=1
            else:
                break
    else:
        for i in reversed(ordered):
            if i > t:
                count +=1
            else:
                break


    unordered.remove(t)
    ordered.append(t)
    ordered.sort()


print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(input()) for _ in range(n)]
p, q = nums.index(1), nums.index(n)
a, b = 1, 1
keep = []

for i in range(2, n+1):
    if  p < nums.index(i):
        a += 1
    else:
        keep.append(a)
        a = 1
    p = nums.index(i)
keep.append(a)
for j in range(n, 0, -1):
    if  q > nums.index(j):
        b += 1
    else:
        keep.append(b)
        b = 1
    q = nums.index(j)
keep.append(b)
print(n - max(keep))

Submission status: Time Limit Exceeded

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


lsi = list(0 for _ in range(n+1))

for i in range(n):
    num = p[i]
    lsi[num] = 1

    for j in range(num):
        if j + lsi[j] == num:
            lsi[j] += 1

print(n - max(lsi))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
number_list = [[int(input())]]
max_length = 1
for i in range(n-1):
  temp = int(input())
  for nl in number_list:
    if nl[-1] == temp-1:
      nl.append(temp)
      if len(nl) > max_length:
        max_length = len(nl)
      temp = 0
      break
  if temp != 0:
    number_list.append([temp])

print(n-max_length)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

P = [int(input()) for _ in range(N)]
P2 = list(P)
l = 0
i = 0
k = 0
        
while len(P):
    num = P2[i]
    k += 1
    P.remove(num)
    try:
        i = P2[i:].index(num+1)+i
    except ValueError:
        P2 = list(P)
        l = max(l,k)
        i = 0
        k = 0
        
print(N - l)

Submission status: Time Limit Exceeded

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 = sorted(P)

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

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

Submission status: Time Limit Exceeded

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

check = [0] * N
wantnext = {}
for i in range(1, N+1):
    wantnext[i] = set([i])

for i in P:
    for j in wantnext[i]:
        check[j-1] += 1
        if i < N:
            wantnext[i+1].add(j)

print(N-max(check))

Submission status: Time Limit Exceeded

Solution code:

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


lsi = list(0 for _ in range(n+1))

for i in range(n):
    num = p[i]
    lsi[num] = 1

    for j in range(n+1):
        if j + lsi[j] == num:
            lsi[j] += 1

print(n - max(lsi))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(input()) for _ in range(n)]
p, q = nums.index(1), nums.index(n)
a, b = 1, 1
keep = []

for i in range(2, n+1):
    if  p < nums.index(i):
        a += 1
        keep.append(a)
    else:
        keep.append(a)
        a = 1
    p = nums.index(i)
for j in range(n, 0, -1):
    if  q > nums.index(j):
        b += 1
        keep.append(b)
    else:
        keep.append(b)
        b = 1
    q = nums.index(j)

print(n - max(keep))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
number_list = [[int(input())]]
for i in range(n-1):
  temp = int(input())
  for nl in number_list:
    if nl[-1] == temp-1:
      nl.append(temp)
      temp = 0
      break
  if temp != 0:
    number_list.append([temp])

count = n

for nl in number_list:
  size = len(nl)
  if count > n - size:
    count = n - size

print(count)

Submission status: Time Limit Exceeded

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

    # asc
    asc_num = 0
    target = 1
    P_tmp = []
    while target <= N:
        tmp_asc_num = 0
        for P_i in P:
            if P_i == target:
                target += 1
                tmp_asc_num += 1
            else:
                P_tmp.append(P_i)
        P = P_tmp[:]
        P_tmp = []
        asc_num = max(asc_num, tmp_asc_num)

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = input()
arr = []
for i in range(n):
	arr.append(input())
i = (n / 2) + 1
count = 0
while(i <= n):
	if arr[i - 1] != i and arr[-1] != i :
		arr.append(i)
		arr.remove(i)
		count = count + 1
	i = i + 1	
i = n / 2
while(i > 0):
	if arr[0] != i and arr[i - 1] != i:
		arr.remove(i)
		arr.insert(0, i)
		count = count + 1
	i = i - 1	
print(count)

Submission status: Time Limit Exceeded

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

#splitされた連続数列の最長を求める
a = []
b = []
for i in p:
    if a == []:
        a.append(i)
        b.append(i)
    elif a[bisect.bisect(a, i)-1]+1==i:
        a[bisect.bisect(a, i)-1] = i
    else:
        bisect.insort(a, i)
        bisect.insort(b, i)

maxi = 0
for a_i, b_i in zip(a, b):
    maxi = max(maxi, a_i+1-b_i)
    
print(N-maxi)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

l = list(range(N))

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

# print(l)

count_l = []

for k in range(N):
    # print("k = {}".format(k))
    count = 1
    st_num = l[k]

    for num in l[k+1:N]:
        # print("num = {}".format(num))
        if num == st_num + 1:
            # print(num)
            count += 1
            st_num += 1

    count_l.append(count)

# print(count_l)

print(N - max(count_l))

Submission status: Time Limit Exceeded

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

def solve():
    # asc
    asc_num = 0
    target = 1
    while target <= N:
        tmp_asc_num = 0
        for P_i in P:
            if P_i == target:
                target += 1
                tmp_asc_num += 1
        asc_num = max(asc_num, tmp_asc_num)

    # desc
    desc_num = 0
    target = N
    while target > 0:
        tmp_desc_num = 0
        for P_i in reversed(P):
            if P_i == target:
                target -= 1
                tmp_desc_num += 1
        desc_num = max(desc_num, tmp_desc_num)

    print(min(N-asc_num, N-desc_num))



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

n =int(input())
g = [int(input()) for i in range(n)] 

a=[0]*n
for i in range(1,n+1,1):
    t=g[:]
#    print(t)
    kai = 0
    ok1 = 1
    ok2 = 1
    for j in range(0,i,1):
        if t[j] != j:
            ok1=0
            break
    for j in range(i,0,-1):
        if ok1 == 1:
            break
        if t[0] != j:
            kai += 1
            t.remove(j)
            t.insert(0,j)
    #
    for j in range(i+1,n+1,1):
        if t[j-1] != j:
            ok2=0
            break
    for j in range(i+1,n+1,1):
        if ok2 == 1:
            break
        if t[n-1] != j:
            kai += 1
            t.remove(j)
            t.append(j)
    a[i-1] = kai 

print(min(a))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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


l = []
i = 0
k = 0
d = 0
while len(P):
    num = P[i+d]
    i += d
    k += 1
    P.remove(num)
    try:
        d = P[i:].index(num+1)
    except ValueError:
        l.append(k)
        i = 0
        k = 0
        d = 0
print(N - max(l))

Submission status: Time Limit Exceeded

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)
for i in range(n):
    check = i+1
    for j in range(n):
        if p[j] == check:
            count[i] += 1
            check += 1

#print count

#print np.max(count)

ans = n-np.max(count)

print ans

Submission status: Time Limit Exceeded

Solution code:


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

    xx = [None] * n
    for s in range(n - 1, -1, -1):
        if xx[s] is not None:
            continue
        count = 1
        pre = pp[s]
        for i in range(s+1, n):
            if pre + 1 == pp[i]:
                if xx[i] is not None:
                    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: Accepted

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

# 数列を並び替えたとき、元のインデクス位置が単調増加となる区間は取り出し不要
# n - 最長区間を引いたものが最短手数となる
p_with_index = list(sorted(enumerate(p), key=lambda x : x[1]))
max_inc_span = 1
span = 1
for i in range(1, n):
    if p_with_index[i-1] < p_with_index[i]:
        span += 1
        max_inc_span = max(max_inc_span, span)
    else:
        span = 1

print(n - max_inc_span)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc024/tasks/agc024_b
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    # 入力
    n = input_int()
    dp = [0] * (n + 1)
    # 解法 -> 最長の連続部分列を求めればよい
    # {1,3,4,5,2,7,6} => {3,4,5}

    for _ in range(n):
        a = input_int()
        dp[a] = dp[a - 1] + 1

    ans = n - max(dp)
    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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=[1]
  
for x in range(n-1):
  if ans[x]<ans[x+1]:
    ch+=1
    
  else:
    ans1.append(ch)
    ch=1
  
  if x==n-2:
    ans1.append(ch)
  
    
print(n-max(ans1))

Submission status: Accepted

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

for i in range(n):
    q[p[i]]=i+1
cnt=1
curcnt=0
for i in range(1,n+1):
    if q[i]>q[i-1]:
        curcnt+=1
        cnt=max(cnt,curcnt)
    else:
        curcnt=1

print(n-cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    p = []
    for _ in range(n):
        p.append(int(input()))
    q = [0 for i in range(n)]
    for i in range(n):
        q[p[i]-1] = i
    m,cnt = 1,1
    for i in range(1,n):
        if q[i]>q[i-1]:
            cnt += 1
            if cnt > m:
                m = cnt
        else:
            cnt = 1
    print(n-m)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
p=[]
for i in range(n):
  p.append((int(input()),i))
p.sort()
l=-1
s=0
mx=0
for i in range(n):
  if p[i][1]>l:
    s+=1
    mx=max(mx,s)
  else:
    s=1
  l=p[i][1]
print(n-mx)

Submission status: Accepted

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

dp = [0 for _ in range(N+1)]

for p in P:
    dp[p] = dp[p-1]+1
    
print(N-max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n= int(input())
p=[int(input())-1 for _ in range(n)]
length=[-1]*n
for i in range(n):
    if i==0 or p[i]==0:
        length[p[i]]=0
    else:
        if (pre:=length[p[i]-1])==-1:
            length[p[i]]=0
        else:
            length[p[i]]=length[p[i]-1]+1
print(n-max(length)-1)

Submission status: Accepted

Solution code:
N, *P = map(int, open(0).read().split())
dp = [0] * (N + 1)
for p in P:
    dp[p] = dp[p - 1] + 1
print(N - max(dp))

Submission status: Accepted

Solution code:
N, *P = map(int, open(0).read().split())
pairs = sorted((P[i], i) for i in range(N))

sub = 1
right = 0
for left in range(N):
    while right < N - 1 and pairs[right + 1][1] > pairs[right][1]:
        right += 1

    sub = max(sub, right - left + 1)

    if left == right:
        right += 1
print(N - sub)

Submission status: Accepted

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

arr=[(P[i],i) for i in range(N)]
arr.sort()

i=0
L=0

while(i<N):
    j=i
    while(j<N-1 and arr[j+1][1]>arr[j][1]):
        j+=1
    L=max(L,j-i+1)
    i=j+1
print(N-L)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N = int(input())

T = [0]*N
for i in range(N):
    T[int(input())-1] = i

m = 0
streak = 1
for a,b in zip(T,T[1:]):
    if a < b:
        streak += 1
    else:
        m = max2(m, streak)
        streak = 1
m = max2(m, streak)

print(N-m)

Submission status: Accepted

Solution code:
from collections import Counter

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

lst = [False] * (n + 1)
for num in p:
    bfo = lst[num - 1]
    if bfo:
        lst[num] = bfo
    else:
        lst[num] = num
cnt = Counter(lst).values()
print(n - max(cnt))

Submission status: Accepted

Solution code:
from collections import Counter

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

lst = [-1] * (n + 1)
for num in p:
    bfo = lst[num - 1]
    if bfo == -1:
        lst[num] = num
    elif bfo > 0:
        lst[num] = bfo
cnt = Counter(lst).values()
print(n - max(cnt))

Submission status: Accepted

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

lst = [0] * (n + 1)
for num in p:
    bfo = lst[num - 1]
    if bfo == 0:
        lst[num] = -1
    elif bfo < 0:
        lst[num] = num - 1
        lst[num - 1] -= 1
    elif bfo > 0:
        lst[num] = bfo
        lst[bfo] -= 1
print(n + min(lst))

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    if((p[i]-1) in d):
        d[p[i]] = d[p[i]-1] + 1
    else:
        d[p[i]] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
P = [int(input())-1 for _ in range(n)]
A = [0]*n
for i, p in enumerate(P):
    A[p] = i

#print(A)

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

Submission status: Accepted

Solution code:
import sys
import math
import copy
import random
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]


class BIT():
    # A1 ... AnのBIT(1-indexed)
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    # A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    # Ai += x O(logN)
    def update(self, idx, x):
        # print(idx)
        while idx <= self.n:
            # print(idx)
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)


def solve():
    n = getN()
    li = []
    for i in range(n):
        li.append(getN())

    slis = [0 for i in range(n+10)]

    for num in li:
        slis[num] = slis[num-1] + 1

    print(n - max(slis))


def main():
    n = getN()
    for _ in range(n):
        s = "".join([random.choice(["F", "T"]) for i in range(20)])
        print(s)
        solve(s, 1, 0)

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    P = [I() for _ in range(N)]

    # Pの最長連続増加部分列以外のところを動かす回数が答え
    # 最長連続増加部分列は、各数字を昇順に並べてP内のインデックスを見ればよい
    enum_P = [(i, e) for e, i in enumerate(P)]
    enum_P.sort()
    # print(enum_P)

    cis = []
    tmp = []
    for i in range(N):
        tmp.append(enum_P[i][1])
        if i < N - 1 and enum_P[i][1] > enum_P[i+1][1]:
            cis.append(tmp)
            tmp = []
    cis.append(tmp)

    ans = N - max([len(i) for i in cis])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# backfront
N = int(input())
a = []
for _ in range(N):
    x = int(input())
    a.append((_, x))
a.sort(key=lambda x: x[1])
a.append((-10000000000000000, 10**20))
cnt, now, maxi = 0, -1, 0
for p, v in a:
    if now < p:
        cnt += 1
        now = p
    elif now > p:
        maxi = max(maxi, cnt)
        cnt = 1
        now = p
print(N-maxi)

Submission status: Accepted

Solution code:
n=int(input())
p=[int(input()) for _ in range(n)]
s=set()
for i in p:
  if i-1 in s:s-={i-1}
  s|={i}
s=[0]+sorted(list(s))
ans=n
for i in range(len(s)-1):
  ans=min(ans,n-s[i+1]+s[i])
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
P = [INT() for _ in range(N)]

dp = [0]*(N+1)

for p in P:
	dp[p] = dp[p-1] + 1

print(N-max(dp))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
P = [INT() for _ in range(N)]

cnt = [0]*(N+1)

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

print(N-max(cnt))

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
p = []
for i in range(n):
    num = int(input())
    num -= 1
    p.append(num)

cnt = [0] * n

for i in range(n):
    if p[i] == 0:
        cnt[0] = 1
    else:
        cnt[p[i]] = cnt[p[i] - 1] + 1

max_p = max(cnt)

print(n - max_p)