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:
#!/usr/bin/env python3
import sys

def solve(N: int, P: "List[int]"):
    if N == 1:
        print(1)
        exit()
    Q = [0]*N
    for i in range(N):
        Q[P[i]-1] = i+1
    last = Q[0]
    maxSeries = 1
    for i in range(1,N):
        if Q[i] > last:
            maxSeries += 1
            last = Q[i]

    print(N-maxSeries+1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(N: int, P: "List[int]"):
    if N == 1:
        print(1)
        exit()
    Q = [0]*N
    for i in range(N):
        Q[P[i]-1] = i+1
    last = Q[0]
    maxSeries = 1
    currentSeries =1
    for i in range(1,N):
        if Q[i] > last:
            currentSeries += 1
        else:
            maxSeries = max(maxSeries,currentSeries)
            currentSeries = 1
        last = Q[i]
    print(N-maxSeries)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(N: int, P: "List[int]"):
    Q = [0]*N
    for i in range(N):
        Q[P[i]-1] = i+1
    last = Q[0]
    maxSeries = 1
    currentSeries =1
    for i in range(1,N):
        if Q[i] > last:
            currentSeries += 1
        else:
            maxSeries = max(maxSeries,currentSeries)
            currentSeries = 1
        last = Q[i]
    print(N-maxSeries)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(N: int, P: "List[int]"):
    sum = 0
    begin = False
    beginIndex = 0
    for i in range(N):
        if i+1 < N and P[i] < P[i+1] and not begin:
            beginIndex = i-P[i]+1
            begin = True
        if P[i] != i+1-beginIndex or not begin:
            sum+=1
    print(sum)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    P = [int(input()) for _ in range(N)]
    P_sorted = sorted(P)
    j = 0
    for i in range(N):
        if P[i] == P_sorted[j]:
            j += 1

    k = 0
    for i in range(N)[::-1]:
        if P[i] == P_sorted[N - k - 1]:
            k += 1

    ans = min(N - j, N - k)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

num1 = 1
for e in p:
    if e == num1:
        num1 += 1

num2 = n
for e in p[::-1]:
    if e == num2:
        num2 -= 1

ans = min(n - num1 + 1, num2)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [int(input()) for _ in range(n)]
pi = [(x-1, i) for i, x in enumerate(p)]
pi.sort()
pi.append((n, 0))

l, mxl = 0, 0
for i, x in pi:
    if x < pi[i-1][1]:
        mxl = max(l, mxl)
        l = 0
    l += 1

print(n - mxl)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#backfront
N=int(input())
lists=[int(input()) for _ in range(N)]
#LIS（Longest increasing subsequence)
import bisect
#listsにおける単調増加部分列の長さを返す
#時間計算量（NlogN)

def LIS(lists):
    N=len(lists)
    inf = 10**15
    dp=[inf  for i in range(N+1)]
    #dp[i]= 長さがi+1であるような増加部分列における最終用の最小値
    for i in range(N):
        index=bisect.bisect_left(dp,lists[i])
        dp[index]=lists[i]
    for i in range(N+1):
        if dp[i]==inf:
            return i
            break
print(N+1-LIS(lists))

Submission status: Wrong Answer

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

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

x = 1
for i in range(1,N):
    if Q[i] > Q[i-1]:
        x += 1
    else:
        x = 1

print(N-x)

Submission status: Wrong Answer

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

l=[]
l.append(P[0])
cnt=0
for i in range(1,N):
    if P[i-1]<P[i]:
        l.append(P[i])
    else:
        cnt=max(cnt,len(l))
        l=[]
        l.append(P[i])

ans=N-cnt
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
nums = []
for i in range(N):
    num = int(input())
    dic[num] = i+1
    nums.append(num)
ans = 0
l = 0
for i in range(N-1):
    if dic[i+2] < dic[i+1]:
        ans = max(ans, l)
        l = 0
    else:
        l += 1
print(N-ans-1)

Submission status: Wrong Answer

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]
init_num = base
# baseの位置 > base+1の所できる.
move = 0
while base <= nums[-1]:
    old_i = i
    if base  == N:
        break
    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: Wrong Answer

Solution code:
n = int(input())
p = [0]*n

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

k1, k2 = p[-1], p[0]
sub1, sub2 = n-k1, k2-1

k1 -= 1
k2 += 1
for i in range(n):
  j = n-1-i
  if p[j] > k1:
    pass
  elif p[j] == k1:
    k1 -= 1

  if p[i] < k2:
    pass
  elif p[i] == k2:
    k2 += 1

sub1 += k1
sub2 += n-k2
ans = min([sub1, sub2])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [0]*n

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

k1, k2 = p[-1], p[0]
sub1, sub2 = n-k1, k2-1

k1 -= 1
k2 += 1
for i in range(n):
  j = n-1-i
  if p[j] > k1:
    pass
  elif p[j] == k1:
    k1 -= 1

  if p[i] < k2:
    pass
  elif p[i] == k2:
    k2 += 1

sub1 += k1
sub2 += n-k2+1
ans = min([sub1, sub2])
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
lis = [int(input()) for i in range(n)]
if lis[0] != 0:print(-1);exit()
ans = 0
num = 0
for i in range(n-1,0,-1):
    if lis[i] > 0:
        ans += lis[i]
        num += lis[i]-1
        lis[i-1] = max(0,lis[i-1]-num)
        lis[i] = 0
        num = max(0,num-1)
  #     print(lis,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [int(input()) for i in range(n)]
li = [-1 for i in range(n)]
for i in range(n):
    li[lis[i]-1] = i
cnt = 0
ans = n-1
for i in range(n-1):
    if li[i] > li[i+1]:
        cnt += 1
    else:
        ans = min(ans,n-1-cnt)
        cnt = 0
ans = min(ans,n-1-cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [int(input()) for i in range(n)]
li = [-1 for i in range(n)]
for i in range(n):
    li[lis[i]-1] = i
cnt = 0
for i in range(n-1):
    if li[i] > li[i+1]:
        cnt += 1
    else:
        cnt = 0
print(n-1-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [int(input()) for i in range(n)]
li = [-1 for i in range(n)]
for i in range(n):
    li[lis[i]-1] = i
ans = 0
for i in range(n-1):
    if li[i] > li[i+1]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
p = [int(readline()) for _ in range(n)]
memo = [0] * n
for i, pp in enumerate(p):
    memo[pp - 1] = i
cnt = 1
ans = 0
for bf, af in zip(memo, memo[1:]):
    if bf < af:
        cnt += 1
    else:
        if ans < cnt:
            ans = cnt
        cnt = 1
print(n - ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n=int(input())
P=[int(input()) for _ in range(n)]
A=[P[0]]
for i in range(1,n):
    if A[-1]<P[i]:A.append(P[i])
    else:A[bisect_left(A,P[i])]=P[i]
print(len(A)+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n=int(input())
P=[int(input()) for _ in range(n)]
A=[P[0]]
for i in range(1,n):
    if A[-1]<P[i]:A.append(P[i])
    else:A[bisect_left(A,P[i])]=P[i]
print(n-len(A)+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n=int(input())
P=[int(input()) for _ in range(n)]
A=[P[0]]
for i in range(1,n):
    if A[-1]<P[i]:A.append(P[i])
    else:A[bisect_left(A,P[i])]=P[i]
print(len(A)-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
P=[int(input()) for _ in range(n)]
cnt,num=0,n

for i in P[::-1]:
    if i==num:num -=1
    else:cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n = int(input())
    idx = [-1] * n
    for i in range(n):
        p = int(input())
        p -= 1
        idx[p] = i
    
    ans = 1
    tmp = 1
    for i in range(1,n):
        if idx[i - 1] < idx[i]:
            tmp += 1
        else:
            ans = max(ans,tmp)
            tmp = 1

    print(n - ans)

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import groupby

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

dic={i:0 for i in range(1,N+1)}
data=['No' for i in range(0,N)]
for i in range(0,N):
    test=P[i]
    if test!=N:
        if dic[test+1]==0:
            data[test-1]='Yes'
    dic[test]+=1

data=groupby(data)
ans=0
for key,group in data:
    g=len(list(group))
    if key=='Yes':
        ans=max(ans,g+1)

print(N-ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    p = IR(n)
    q = [None for i in range(n + 1)] + [-1]
    for i in range(n):
        q[p[i]] = i
    ans = 0
    tmp = 0
    for i in range(2, n + 2):
        if q[i - 1] < q[i]:
            continue
        ans = max(ans, i - tmp)
        tmp = i
    print(n-ans)
    return
#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    p = IR(n)
    q = [None for i in range(n + 1)] + [-1]
    for i in range(n):
        q[p[i]] = 1
    ans = 0
    tmp = 0
    for i in range(2, n + 2):
        if q[i - 1] < q[i]:
            continue
        ans = max(ans, i - tmp)
        tmp = i
    print(n-ans)
    return
#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    p = IR(n)
    q = [p[i] for i in range(n)]
    ans = 0
    tmp = 0
    for i in range(1, n):
        if q[i - 1] < q[i]:
            ans = max(ans, i - tmp)
            continue
        ans = max(ans, i - tmp)
        tmp = i
    print(n-ans)
    return
#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    p = IR(n)
    dm = [inf]
    dx = [-1]
    for i in range(n):
        dx.append(max(dx[-1], p[i]))
    for j in range(n):
        dm.append(min(dm[-1], p[-j - 1]))
    dm = dm[::-1]
    ans = 0
    l = 0
    for i in range(n - 1, 0, -1):
        if dx[i] > p[i] or l > p[i]:
            l = max(l , p[i])
            ans += 1
    if p[0] < l:
        ans += 1
    tmp = 0
    l = inf
    for i in range(n - 1):
        if dm[i] < p[i] or l < p[i]:
            l = min(p[i], l)
            tmp += 1
    if l < p[-1]:
        tmp += 1
    print(min(ans, tmp))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

tmp = 1
num = 0

for i in range(n):
    if pi[i] == tmp:
        tmp += 1
        num += 1
        
left = n-num

num = 0
tmp = n

for i in range(n):
    if pi[n-1-i] == tmp:
        tmp -= 1
        num += 1

right = n-num
print(min(left,right))

Submission status: Wrong Answer

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

up = 0
down = 0
for i in range(N):
    if P[i] == up+1:
        up += 1
    
    if P[-1-i] == N-down:
        down += 1

print(N - max(up, down))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

for i in range(N):
    idx[P[i]] = i
    
dp = [0]*N

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

print(N-max(dp))

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline())

P = [int(sys.stdin.readline()) for _ in range(N)]
prv_p = 0
ans1 = 0
for p in P:
    if prv_p > p:
        ans1 = max(ans1, p)
    else:
        prv_p = p

prv_p = 0
ans2 = 0
for p in P[::-1]:
    if prv_p < p:
        ans2 = max(ans2, p)
    else:
        prv_p = p

print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline())

P = [int(sys.stdin.readline()) for _ in range(N)]
prv_p = 0
ans1 = 0
for p in P:
    if prv_p > p:
        ans1 = max(ans1, p)
    else:
        prv_p = p

prv_p = 0
ans2 = 0
for p in P[::-1]:
    if prv_p > p:
        ans2 = max(ans2, p)
    else:
        prv_p = p

print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline())
ans = 0
prv_p = 0
for _ in range(N):
    p = int(sys.stdin.readline())
    if prv_p > p:
        ans = max(ans, p)
    else:
        prv_p = p
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
p=[int(input())for _ in range(n)]
cnt1=1
for i in range(n):
	if p[i]==cnt1:
		cnt1+=1
cnt2=n
for i in range(n-1,-1,-1):
	if p[i]==cnt2:
		cnt2-=1
print(n-max(cnt1-1,n-cnt2))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[int(input()) for i in range(n)]
li=[0 for i in range(n+1)]
for i,j in enumerate(l):
    li[j]=i
ans=n-1
i=1
ms=1
while i<n:
    if li[i]<li[i+1]:
        ms+=1
        i+=1
    else:
        ans=min(ans,n-ms)
        ms=1
        i+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

root=[-1]*N
count=[0]*N
for item in P:
    if item == 0:
        root[item]=item
        continue
    if root[item-1]==-1:
        root[item]=item
        count[root[item]]+=1
    else:
        root[item]=root[item-1]
        count[root[item]]+=1
"""
print(root)
print(count)
print("===========================")
"""
print(N-max(count))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N=int(input())

P=[]

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

P_alt=P[::-1]
#print(P)
#print(P_alt)

ans=[N]
while P:
    temp=P.pop(-1)
    if temp==ans[-1]:
        ans.append(temp-1)

ans_alt=[1]
while P_alt:
    temp=P_alt.pop(-1)
    if temp==ans_alt[-1]:
        ans_alt.append(temp+1)

print(min(ans[-1],N+1-ans_alt[-1]))

Submission status: Wrong Answer

Solution code:
N=int(input())

P=[]

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

#print(P)

ans=[N]
while P:
    temp=P.pop(-1)
    if temp==ans[-1]:
        ans.append(temp-1)

print(ans[-1])

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
dp = [A[0]]
for i in A[1:]:
    if i > dp[-1]:
        dp.append(i)
    else:
        dp[bisect.bisect_right(dp,i)] = i     
print(N-len(dp)+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for i in range(N)]
nmax = P[0]
ans = 0
for i in range(1,N):
    if nmax > P[i]:
        ans = max(ans,P[i])
    nmax = max(nmax,P[i])
print(ans)

Submission status: Wrong Answer

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

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

ans = N-max(L)-1
print(ans)

Submission status: Wrong Answer

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

num = P[0]
ans = num-1
for i in range(1, N):
    if P[i] == num+1:
        num += 1
    elif P[i] > num+1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

import bisect
inf = 10**6
L = [inf]*N
num = 0
for p in P:
    idx = bisect.bisect_left(L, p)
    if idx >= num:
        L[idx] = p
        num = idx

ans = N
for i in range(N):
    if L[i] < inf:
        idx = i
    else:
        break
ans -= idx+1
if L[0] == 1 or L[idx] == N:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

ma = 0
s = 0
for i in range(1, N):
    if X[i] < X[i-1]: s = i
    ma = max(ma, i - s + 1)

print(N - ma)

Submission status: Wrong Answer

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

ma = 0
s = X[0]
for i in range(1, N):
    if X[i] < X[i-1]: s = i
    ma = max(ma, i - s + 1)

print(N - ma)

Submission status: Wrong Answer

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

ma = 0
s = X[0]
for i in range(1, N):
    ma = max(ma, i - s)
    if X[i] < X[i-1]: s = i

print(N - ma)

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inn())
l = 0
for i in range(n):
    if a[i]==l+1:
        l += 1
r = n+1
for i in range(n-1,-1,-1):
    if a[i]==r-1:
        r -= 1
print(min(n-l,r-1))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
# 順列のindexを手に入れる。
index_permutation = {}
for i in range(N):
    index_permutation[i] = P[i]

# valueの昇順が崩れる場所で分ける
now = index_permutation[0]
max_len = 0
tmp = 1
for p in list(index_permutation.values())[1:]:
    if p > now:
        tmp += 1
        now = p
    else:
        max_len = max(tmp, max_len)
        now = p
        tmp = 1
print(N-max_len)

Submission status: Wrong Answer

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

q = [0] * n
for i in range(n):
    q[p[i]-1] = i
mxk = 1
k = 1
for i in range(n-1):
    if q[i] < q[i+1]:
        k += 1
        if k > mxk:
            mxk = k
    else:
        k = 1
print(n-k)

Submission status: Wrong Answer

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

P = [0] * (N+1)
for i in range(N):
  P[A[i]] = i+1
  
work = 0 
maxw = 0
for i in range(1,N):
  if P[i] < P[i+1]:
    work += 1
    maxw = max(maxw, work)
  else:
    work = 1
    
print(N - maxw)

Submission status: Wrong Answer

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

ascN,ascC = 1,0
descN,descC = N,0

for i in range(N):
  a = A[i]
  if a == ascN:
    ascN += 1
    ascC += 1
    
for i in range(N-1,-1,-1):
  a = A[i]
  if a == descN:
    descN -= 1
    descC += 1
    
print(N-max(ascC, descC))

Submission status: Wrong Answer

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

O=[0]*(N)
for i,p in enumerate(P): O[p-1]=i

n=1
nn=0
for i in range(1,N):
    if O[i-1]<O[i]: n+=1
    else: n=1
    nn=max(nn,n)

print(N-nn)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[int(input()) for _ in range(N)]
m=0
ans1=0
for p in P:
    if m>p:
        ans1=max(ans1,p)
    else:
        m=p
m=10**6
ans2=10**6
for p in reversed(P):
    if m<p:
        ans2=min(ans2,p)
    else:
        m=p
print(min(ans1,N-ans2+1))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="number"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True

fac=fac_list(10**5+100,mod)
def C(n,r):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod

 
#main
N=int(input())
Q=[0]*N
for a in range(N):
    Q[int(input())-1]=a

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