Problem:


Score : 500 points

Problem Statement

You are given a sequence (P_1,P_2,...,P_N) which is a permutation of the integers from 1 through N.
You would like to sort this sequence in ascending order by repeating the following operation:

Choose an element in the sequence and move it to the beginning or the end of the sequence.

Find the minimum number of operations required.
It can be proved that it is actually possible to sort the sequence using this operation.

Constraints

1 \leq N \leq 2\times 10^5

(P_1,P_2,...,P_N) is a permutation of  (1,2,...,N).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1
:
P_N

Output

Print the minimum number of operations required.

Sample Input 1

4
1
3
2
4

Sample Output 1

2

For example, the sequence can be sorted in ascending order as follows:

Move 2 to the beginning. The sequence is now (2,1,3,4).

Move 1 to the beginning. The sequence is now (1,2,3,4).

Sample Input 2

6
3
2
5
1
4
6

Sample Output 2

4

Sample Input 3

8
6
3
1
2
7
4
8
5

Sample Output 3

5



Sample input:
4
1
3
2
4


Sample output:
2

Submission status: Wrong Answer

Solution code:
n=int(input())

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

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
P = [int(input()) for _ in range(N)]
INF = 10**15

dp = [INF for _ in range(N)]

for p in P:
    idx = bisect.bisect_left(dp, p)
    dp[idx] = min(dp[idx], p)
    
print(N-bisect.bisect_left(dp, INF)+1)

Submission status: Wrong Answer

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

L=0
s=1
for i in range(N):
    if P[i]==s:
        L+=1
        s+=1
R=0
s=N
for i in reversed(range(N)):
    if P[i]==s:
        R+=1
        s-=1
print(N-max(L,R))

Submission status: Wrong Answer

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

print(N-streak)

Submission status: Wrong Answer

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] = num
    else:
        lst[num] = bfo
cnt = Counter(lst).values()
print(n - max(cnt))

Submission status: Wrong Answer

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] = num
    elif bfo > 0:
        lst[num] = bfo
cnt = Counter(lst).values()
print(n - max(cnt))

Submission status: Wrong Answer

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] = num - 1
cnt = Counter(lst).values()
print(n - max(cnt))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
plist = []
for i in range(N):
    x = int(input())
    plist.append(x)
right = plist[-1]
cnt = 0
cur = right
ind = -1000
for i in reversed(range(N-1)):
    if(plist[i] > right):
        cnt += 1
    elif(cur - plist[i] > 1):
        ind = i
        break
    else:
        cur = plist[i]

print(ind+cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
plist = []
for i in range(N):
    x = int(input())
    plist.append(x)
right = plist[-1]
print(right)
cnt = 0
cur = right
ind = -1000
for i in reversed(range(N-1)):
    if(plist[i] > right):
        cnt += 1
    elif(cur - plist[i] > 1):
        ind = i
        break
    else:
        cur = plist[i]

print(ind+cnt)

Submission status: Wrong Answer

Solution code:
import random
print(random.randint(1,10**6))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    
    n=I()
    list_=LI2()
    dict_=defaultdict(lambda:x)
    for i in range(n):
        dict_[list_[i]]=i
    mx=0
    length=1
    for i in range(1,n):
        if dict_[i]<dict_[i+1]:
            length+=1
        else:
            mx=max(length,mx)
            length=1
    print(n-mx)
    
    



if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())

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

ll=1
ll_cnt=0

for item in a:
    if item==ll:
        ll_cnt+=1
        ll+=1

rr=n
rr_cnt=0
a=a[::-1]

for item in a:
    if item==rr:
        rr_cnt+=1
        rr-=1

print(n-max(rr_cnt,ll_cnt))

Submission status: Wrong Answer

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    Q = [0]*N
    for i in range(N):
        Q[read_int()-1] = i
    max_k = 1
    k = 1
    for i in range(1, N):
        if Q[i] > Q[i-1]:
            k += 1
            max_k = max(max_k, k)
        else:
            k = 1
    return N-k


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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

isAfter=0
isBefore = 0

isFirst = 1 if P[0]==1 else 0
isLast = 1 if P[-1]==N else 0

if N == 1:
    print(0)
    exit()
else:
    P.remove(1)
    P.remove(N)

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

ope = isAfter + isBefore + (isAfter==0 and isLast == 0)+(isBefore==0 and isFirst == 0)

print(ope)

Submission status: Wrong Answer

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
try:
    P.remove(1)
    P.remove(N)
except:
    print(0)
    exit()

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

Solution code:
import sys
input = sys.stdin.readline
import heapq


def read():
    N = int(input().strip())
    P = []
    for i in range(N):
        p = int(input().strip())
        P.append(p)
    return N, P


def solve(N, P):
    Q = [0 for i in range(N+1)]
    for i in range(N):
        Q[P[i]] = i
    max_count = 0
    count = 0
    prev = -1
    for i in range(N):
        q = Q[i]
        if prev < q:
            count += 1
            prev = q
        else:
            max_count = max(max_count, count)
            count = 1
            prev = q
    max_count = max(max_count, count)
    return N - max_count


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq


def read():
    N = int(input().strip())
    P = []
    for i in range(N):
        p = int(input().strip())
        P.append(p)
    return N, P


def solve(N, P):
    h = []
    for i in range(N):
        heapq.heappush(h, (P[i], i+1))
    max_count = 0
    count = 0
    prev = -1
    for _ in range(N):
        p, i = heapq.heappop(h)
        if prev < i:
            count += 1
            prev = i
        else:
            max_count = max(max_count, count)
            count = 1
            prev = i
    return N - max_count


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

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

now = 1
cnt1 = 0
for i in range(N):
    if P[i] == now:
        now += 1
        cnt1 += 1

now = N
cnt2 = 0
for i in range(N-1,-1,-1):
    if P[i] == now:
        now -= 1
        cnt2 += 1

print(N-max(cnt1, cnt2))

Submission status: Wrong Answer

Solution code:
N=int(input())

a1=int(input())
ans=a1-1
for i in range(N-1):
    a=int(input())
    if a<=a1:continue
    elif a==a1+1:
        a1=a
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

    n_down = 0
    num = 1
    for p in P:
        if p == num:
            n_down += 1
            num += 1
    
    n_up = 0
    num = N
    for p in P[::-1]:
        if p == num:
            n_up += 1
            num -= 1

    ans = N - max(n_down, n_up)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

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

cnt = 1
now_idx = -1
ans = 0
for i in range(N):
    idx = Q[i]
    if idx>now_idx:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 1
    now_idx = idx
print(N-ans)

Submission status: Wrong Answer

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

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

    ans = 1
    pre = Q[1]
    cur = 1
    for q in Q[2:]:
        if pre < q:
            cur += 1
        else:
            ans = max(ans, cur)
            cur = 1
        pre = q
    print(N - ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

count = 0
ans = 0
s = set()
for i in range(N):
    while 1:
        if count+1 in s:
            count += 1
        else:
            break
    p = int(input())
    if p==count+1:
        count += 1
    else:
        if p<N//2:
            ans += p-1
            s.add(p)
        else:
            ans += 1
            s.add(p)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from bisect import bisect_right
lis = []
max_lis = []
for i in range(N):
    p = Ps[i]
    idx = bisect_right(lis, p)
    if idx>=len(lis):
        lis.append(p)
        max_lis = lis.copy()
    elif idx==len(lis)-1:
        lis[idx] = p
        max_lis = lis.copy()
    else:
        lis[idx] = p

s = set(max_lis)
now_idx = 0
cnt = 0
for i in range(N):
    p = Ps[i]
    if p in max_lis:
        pass
    else:
        if p<N//2:
            cnt += p-1
        else:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
INF = 10**9 + 7


def main():
    from bisect import bisect_left
    N = int(input())
    P = [int(input()) for i in range(N)]

    dp1 = [INF]*(N)
    for i in range(N):
        idx = bisect_left(dp1, P[i])
        dp1[idx] = P[i]

    dp2 = [INF]*(N)
    for i in range(N)[::-1]:
        idx = bisect_left(dp2, N-P[i]+1)
        dp2[idx] = N-P[i]+1

    ma = 0
    for i, v in enumerate(dp1, start=1):
        if i != v:
            break
        ma += 1
    ans = ma
    ma = 0
    for i, v in enumerate(dp2, start=1):
        if i != v:
            break
        ma += 1
    ans = max(ans, ma)
    print(N - ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
  temp = int(input())
  A.append(temp)
first = A[0]
now = A[0]
ans = 0
for i in range(1,N):
  if first > A[i]: #最初の左端よりも小さい場合
    ans += 1
  elif now > A[i]: #単調増加に反する場合
    ans += 2
  else: 
    now = A[i]
print(ans)

Submission status: Wrong Answer

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

D = {p:i for i,p in enumerate(P)}
pv = N
l = seq = 0
for n in range(1,N+1):
    nx = D[n]
    if pv < nx:
        seq += 1
    else:
        l = max(l,seq)
        seq = 1
    pv = nx

print(N - l)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = [int(input()) for i in range(N)]
    for i, p in enumerate(P[::-1]):
        if N - i != p:
            print(p)
            break


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a = 1
for p in P:
    if p==a:
        a += 1

b = N
for p in P[::-1]:
    if p==b:
        b -= 1

print(min(N-a+1, b))

Submission status: Wrong Answer

Solution code:
from bisect import*

n, *p = map(int, open(0))

def LIS(seq):
  L = [seq[0]]
  for i in range(len(seq)):
    if seq[i] > L[-1]:L += seq[i],
    else:L[bisect_left(L, seq[i])] = seq[i]
  return len(L)

print(n - LIS(sorted(range(n), key = lambda s:p[s])) + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
Ps = [int(input())for _ in range(n)]
p_to_i = {p: i for i, p in enumerate(Ps)}

cnt = 0
x = 1
for p in range(1, n):
    if p_to_i[p] < p_to_i[p+1]:
        x += 1
        if cnt < x:
            cnt = x
    else:
        x = 1
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
Ps = [int(input())for _ in range(n)]
p_to_i = {p: i for i, p in enumerate(Ps)}

x = 1
for p in range(1, n):
    if p_to_i[p] < p_to_i[p+1]:
        x += 1
    else:
        x = 1
print(n-x)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for _ in range(n)]
coun = 0
l_r = l[::-1]
num = n
for i in range(n):
  if l_r[i]==num:
    num -= 1
  else:
    coun += 1
print(coun)

Submission status: Wrong Answer

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

cnt = 0
idx = n
for p in reversed(Ps):
    if p == idx:
        idx -= 1
        cnt += 1
a1 = n-cnt

cnt = 0
idx = 1
for p in Ps:
    if p == idx:
        idx += 1
        cnt += 1
a2 = n-cnt
print(min(a1, a2))

Submission status: Wrong Answer

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

cnt = 0
idx = n
for p in reversed(Ps):
    if p == idx:
        idx -= 1
        cnt += 1

print(n-cnt)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    P = list(in_all())
    Q = [0] * (N + 1)

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

    dc = []
    for i in range(1, N):
        if Q[i] < Q[i + 1]:
            dc.append(1)
        else:
            dc.append(0)

    gr = itertools.groupby(dc)

    cnt = 0
    for k, v in gr:
        v = sum(1 for _ in v)
        if k == 1:
            cnt = max(cnt, v + 1)

    print(N - cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
p=[int(input()) for _ in range(n)]
res=[0]*n
for i in range(n):
    res[p[i]-1]=i

k=1
x=0
for i in range(1,n):
    if res[i-1]<res[i]:
        k+=1
    else:
        x=max(x,k)
        k=1
print(n-x)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

mid = np.median(p)

low = []
up = []
for i in range(n):
    if p[i] < mid:
        low.append(p[i])
    else:
        up.append(p[i])

ans = 0
m = 0
for l in low:
    if l >= m:
        m = l
    else:
        ans += 1

for u in up:
    if u >= m:
       ans += 1
       m = u
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

mid = np.median(p)

low = []
up = []
for i in range(n):
    if p[i] < mid:
        low.append(p[i])
    else:
        up.append(p[i])

ans = 0
m = 0
for l in low:
    if l > m:
        m = l
    else:
        ans += 1

for u in up:
    if u > m:
       ans += 1
       m = u

print(ans)

Submission status: Wrong Answer

Solution code:
"""
連続する数は動かさず、それ以外を左右に分配していく
⇨並べ替えた後、昇順に連続しているかは、インデックスが昇順になっているかを見る
"""
import sys
input = sys.stdin.readline

n = int(input())
ps = {int(input()):i for i in range(n)}

cnt = 1
prev = 10**10
ans = 0
for i in range(1,n+1):
    ind = ps[i]
    # print(i,ind)
    if prev < ind:
        cnt += 1
    else:
        ans = max(ans, cnt)
        cnt = 1
    prev = ind
print(n-ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
ps = {int(input()):i for i in range(n)}

cnt = 1
prev = 1000
ans = 0
for i in range(1,n+1):
    ind = ps[i]
    # print(i,ind)
    if prev < ind:
        cnt += 1
    else:
        ans = max(ans, cnt)
        cnt = 1
    prev = ind
print(n-ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

cnt = 0
now = n
for p in ps[::-1]:
    if p == now:
        now -= 1
m1 = now
now = 1
for p in ps:
    if p == now:
        now += 1
m2 = n - now + 1
# print(m1,m2)
print(min(m1,m2))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

cnt = 0
now = n
for p in ps[::-1]:
    if p == now:
        now -= 1
now = 1
for p in ps:
    if p == now:
        now += 1

print(min(now,n-now+1))

Submission status: Wrong Answer

Solution code:
"""
大きい方から見ていって、降順が成り立っているのはどこまでか
"""
import sys
input = sys.stdin.readline

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

cnt = 0
now = n
for p in ps[::-1]:
    if p == now:
        now -= 1
print(now)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    P = list(int(input()) for _ in range(n))

    num = n
    res1 = 0
    for i in reversed(range(n)):
        if P[i] != num:
            res1 += 1
        else:
            num -= 1

    num = 1
    res2 = 0
    for i in range(n):
        if P[i] != num:
            res2 += 1
        else:
            num += 1

    print(min(res1, res2))


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    P = list(int(input()) for _ in range(n))

    num = n
    res = 0
    for i in reversed(range(n)):
        if P[i] != num:
            res += 1
        else:
            num -= 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
p = [0 for _ in range(N)]
for i in range(N):
  A[i] -= 1
  p[A[i]] = i
m = 0
prev = -1
cnt = 0
for i in range(N):
  if p[i] > prev:
    cnt += 1
  else:
    m = max(m, cnt)
    cnt = 1
  prev = p[i]
print(N-m)

Submission status: Wrong Answer

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
if c==set():
    print(0)
else:
    print(n-max(c))

Submission status: Wrong Answer

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 = {1}
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: Wrong Answer

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

from operator import neg

def main():
  n = int(input())
  lp = [int(input()) for _ in range(n)]
  def f(lp):
    c = lp[0]
    ic = 0
    for p in lp[1:]:
      if c < p:
        c = p
      else:
        ic = max(ic, p)
    return ic
  print(min(f(lp), f([n-p+1 for p in lp[::-1]])))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  lp = [int(input()) for _ in range(n)]
  def f(lp):
    c = lp[0]
    ic = 0
    for p in lp[1:]:
      if c < p:
        c = p
      else:
        ic = max(ic, p)
    return ic
  print(min(f(lp), f(lp[::-1])))

if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

def main():
  n = int(input())
  lp = [int(input()) for _ in range(n)]
  c = lp[0]
  ic = 0
  for p in lp[1:]:
    if c < p:
      c = p
    else:
      ic = max(ic, p)
  print(ic)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0]*n
for i in range(n):
    l[int(input())-1]=i
pre=-1
now=0
ans=n
for i in l:
    if pre<i:
        now+=1
    else:
        ans=min(ans,n-now)
        now=1
    pre=i
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
now = 0
won = N + 1
for p, p_ in zip(P, P[::-1]):
    if p == now + 1:
        now = p
    if p_ == won - 1:
        won = p_

print(min(won - 1, N - now))

Submission status: Wrong Answer

Solution code:

N = int(input())

A = []
X = []

for _ in range(N):
    p = int(input())
    if len(A) == 0:
        A.append(p)
        X.append(1)
    elif A[-1] < p:
        A.append(p)
        X.append(1)
    elif p - 1 in A:
        x = A.index(p-1)
        A[x] = p
        X[x] += 1
    else:
        A.append(p)
        X.append(1)
print(N - max(X))

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0
m = 0

for _ in range(N):
    now = int(input())
    if m < now:
        m = max(m, now)
    else:
        ans = max(now, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for i in range(N)]
is_earlier = [True] * (N+1)
is_earlier[-1] = False
appeared = set()
for p in P:
  if p+1 in appeared:
    is_earlier[p-1] = False
  appeared.add(p)

M = 0
now = 0
for i in range(N+1):
    if is_earlier[i]:
        now += 1
    else:
        M = max(M, now)
        now = 0

print(N - M)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
from collections import Counter
dp=[0]*(n+1)
for x in a:
    if x!=1 and dp[x-1]!=0:
        dp[x]=dp[x-1]
    elif x!=1:
        dp[x]=x
    else:
        dp[1]=1
c=Counter(dp)
_, most=c.most_common()[0]
if most>1:
    print(n-most)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import bisect
def lis(a):
	"""
	param a: list
	return: the length of Longest increasing subsequence
	(be careful that [list] seq is not the LIS, but its length is accurate LIS length.)
	"""
	seq = []
	tmp = 0
	for i in a:
		pos = bisect.bisect_left(seq, i)
		if tmp <= pos:
			seq.append(i)
			tmp += 1
		else:
			seq[pos] = i
	return tmp


n = int(input())
p = [int(input()) for _ in range(n)]
print(n-lis(p)+1)

Submission status: Wrong Answer

Solution code:
def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>=key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

# 最長増加部分列
def lis(al):
    n = len(al)
    dp = [10**9]*(n+1)

    for a in al:
        dp[lower_bound(dp, a)] = a
    return lower_bound(dp, 10**9)

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

print(n - lis(al) + 1)

Submission status: Wrong Answer

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


dp = [10**20 for _ in range(N)]
for i in range(N):
    p = bisect.bisect_left(dp, P[i])
    dp[p] = P[i]

for j in range(N-1, -1, -1):
    if dp[j] != 10**20:
        print(N-j)
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
p = []
for _ in range(n):
    p.append(int(input()))
now = 1
for i in p:
    if i==now:
        now += 1
mx = now-1
now = n
for i in reversed(p):
    if i==now:
        now -= 1
mx = max(mx, n-now)
print(n-mx)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = 0 if k - 1 == P[0] else 1
        l += (k - 2) - streak[k - 1]
        if ans > l + r:
            ans = l + r
        # dbg(f"{ans=} {l=} {r=}")
    return ans


print(solve())

Submission status: Wrong Answer

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

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

max1 = P[0]
cnt1 = 1
for i in range(1,N):
    if P[i]>max1:
        if P[i]-max1==1:
            cnt1+=1
        max1=P[i]

min2 = 1
cnt2 = 0
for i in range(1,N):
    if P[i]==min2:
        cnt2+=1
        min2+=1

print(min(N-cnt1,N-cnt2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
p=[int(input())-1 for _ in range(n)]
a=[0]*n
for i in range(n):
    a[p[i]]=i
l=1
ans=1
for i in range(n-1):
    if a[i]<a[i+1]:
        l+=1
    else:
        ans=max(ans,l)
        l=1
print(n-ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = list(int(input()) for _ in range(N))
    
    dp = [0] * (N + 1)
    dp[N] = 1
    for i in range(N-1,-1,-1):
        if P[i] == N:
            continue
        if dp[P[i] + 1] == 0:
            dp[P[i]] = 1
        else:
            dp[P[i]] = dp[P[i] + 1] + 1

    print(N - max(dp))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

left, right = 1, n
for i in range(n):
    if p[i] == left:
        left += 1

for i in reversed(range(n)):
    if p[i] == right:
        right -= 1

#print(left, right)
print(min(n - left + 1, right))

Submission status: Wrong Answer

Solution code:
def main():

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

    d = dict()
    for i in range(N):
        if i == 1:
            d[p[i]] = 1
        else:
            if p[i] - 1 in d:
                d[p[i]] = d[p[i]-1] + 1
            else:
                d[p[i]] = 1
    return N - max(list(d.values()))


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

Submission status: Wrong Answer

Solution code:
n = int(input())

p = []
for _ in range(n):
    p.append(int(input()))
    
p.reverse()
ans = n
check = n
for num in p:
    if num == check:
        ans -= 1
        check -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
dict={}
res=0
for i in range(n):
    dict[int(input())]=i
for i in range(1,n):
    if dict[i]> dict[i+1]:
      res+=1
      if i<(n//2):
        dict[i]=-res     
      elif i>=(n//2):
        dict[i]=n+res  
print(res+1)