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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = ILs(N)

START = []
f = [0 for i in range(N+1)]
for a in A:
  if f[a-1] == 0:
    START.append(a)
    f[a] = 1
  else:
    f[a] = 1
START.sort()
dic = {k:[] for k in START}
for a in A:
  p = bisect.bisect(START,a)
  dic[START[p-1]].append(a)
print(N-max(len(dic[k]) for k in START))

Solution (Python):
n=int(input())
p=[int(input()) for _ in range(n)]
d={}
for pi in p:
  if pi-1 in d:
    d[pi]=d[pi-1]+1
  else:
    d[pi]=1
print(n-max(d.values()))

Solution (Python):
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))

    res = [0] * (n + 1)
    for p in P:
        res[p] = res[p - 1] + 1
    print(n - max(res))


if __name__ == '__main__':
    resolve()

Solution (Python):
n=int(input())
P=[int(input()) for _ in range(n)]
DP=[0 for _ in range(n+1)]

for i in P:
    DP[i]=DP[i-1]+1
print(n-max(DP))

Solution (Python):
n=int(input())
P=[int(input()) for _ in range(n)]
DP=[0]*(n+1)
for i in P:
    DP[i]=DP[i-1]+1
print(n-max(DP))

Solution (Python):
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]
m = max(m, cnt)
print(N-m)

Solution (Python):

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(1,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))

Solution (Python):
N = int(input())
S = [0]*N
for i in range(N):
    a = int(input())
    a -= 1
    if a == 0:
        S[0] = 1
    else:
        if S[a-1] == 0:
            S[a] = 1
        else:
            S[a] = S[a-1] + 1
print(N-max(S))

Solution (Python):
n = int(input())
pl = [int(input()) for _ in range(n)]

d = {}
for i in range(n):
    d[pl[i]] = i

dp = [1]*n
p = 1
while p<n:
    if d[p+1]>d[p]:
        dp[d[p+1]] = dp[d[p]]+1
    p += 1
print(n-max(dp))

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
pl = [-1]*(n+1)

for i in range(n):
    pl[a[i]-1] = i

a = 1
ma = 1
for i in range(n):
    if pl[i] < pl[i+1]:
        a += 1
    else:
        ma = max(a,ma)
        a = 1
        
print(n-ma)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
p = list(map(int,read().split()))
q = [0] * n
for i,p_i in enumerate(p):
    q[p_i-1] = i

longest = 1
now = 1
for i in range(1,n):
    if(q[i] > q[i-1]):
        now += 1
    else:
        now = 1
    longest = max(longest,now)

print(n-longest)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
p = [[int(j),i] for i,j in enumerate(read().split()) ]
p.sort()

longest = 1
now = 1
for i in range(1,n):
    if(p[i][1] > p[i-1][1]):
        now += 1
    else:
        now = 1
    longest = max(longest,now)

print(n-longest)

Solution (Python):



def main():
  n = int(input())
  lp = [int(input()) for _ in range(n)]
  ilp = sorted(enumerate(lp), key=lambda x:x[1])
  max_cnt = 0
  cnt = 1
  for i in range(n-1):
    if ilp[i] < ilp[i+1]:
      cnt += 1
    else:
      max_cnt = max(max_cnt, cnt)
      cnt = 1
  print(n - max(max_cnt, cnt))
  
if __name__=='__main__':
  main()

Solution (Python):
from bisect import bisect_left,bisect
 
n = int(input())
cou = [0 for i in range(n+1)]
for i in range(n):
    now = int(input())
    cou[now] = cou[now-1] + 1  

print(n-max(cou))

Solution (Python):
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(min(ans,n-now))

Solution (Python):
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))

Solution (Python):


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

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

print(N - ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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))


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline()[:-1]
def main():
    n = int(input())
    a = [int(input()) for k in range(n)]
    b = [[a[k],k] for k in range(n)]
    b = sorted(b)
    c = [b[k][1] for k in range(n)]
    c = [-1] + c + [100000]
    t = 0
    ans = 0
    for k in range(1,n+1):
        if c[k-1] < c[k]:
            t += 1
        else:
            t = 1
        ans = max(ans,t)
    print(n-ans)
if __name__ == '__main__':
    main()

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

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

print(N - M)

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    P = []
    for i in range(N):
        P.append((int(input()), i))
    P.sort(key=lambda x: x[0])
    Q = list(zip(*P))[1]
    cnt = 1; ans = 1
    for i in range(N-1):
        if Q[i] < Q[i+1]:
            cnt += 1
        else:
            cnt = 1
        ans = max(ans, cnt)
    print(N-ans)

if __name__ == "__main__":
    main()

Solution (Python):
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]

print(n-most)

Solution (Python):

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

a=[0]*n
cnt=1
ans=0
for i in range(n):
    a[p[i]-1]=i

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

Solution (Python):
n = int(input())
p = []
for _ in range(n):
    p.append(int(input()))
li = [0]*(n+1)
for i in p:
    li[i] = li[i-1]+1
print(n-max(li))

Solution (Python):
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))

Solution (Python):
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()


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


def solve():
    if N == 1:
        return 0

    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
        
    return ans


print(solve())

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

check = [0]*(N+1)
for i in range(N):
    X = P[i]
    check[X] = check[X-1]+1
M = max(check)
print(N-M)

Solution (Python):
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
ans=max(ans,l)
print(n-ans)

Solution (Python):
from collections import defaultdict
n = int(input())
p = [int(input()) for i in range(n)]
d = defaultdict(int)
for i in p:
    d[i] = d[i - 1] + 1
print(n - max(d.values()))

Solution (Python):
from collections import defaultdict

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

c = defaultdict(int)
for Pi in P:
    c[Pi] = c[Pi - 1] + 1

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

Solution (Python):
def main():
    N = int(input())
    P = list(int(input()) for _ in range(N))
    
    dp = [0] * (N + 1)
    for i in range(N-1,-1,-1):
        if P[i] == N:
            dp[P[i]] = 1
            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()

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


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

print(n - max(dp))

Solution (Python):
def main():

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

    d = dict()
    for i in range(N):
        if i == 0:
            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())

Solution (Python):
n = int(input())
li = [int(input()) for _ in range(n)]
ma = {}
for i,l in enumerate(li):
    ma[l] = i+1
nu = []
for j in range(n):
    nu.append(ma[j+1])

ans = [0]
tmp = 0
cnt = 0
for k,u in enumerate(nu):
    if k == 0:
        tmp = u
        cnt += 1
        continue
    if u > tmp:
        tmp = u
        cnt += 1
    else:
        ans.append(cnt)
        tmp = u
        cnt = 1
ans.append(cnt)


print(n - max(ans))

Solution (Python):
n = int(input())

p = []
for _ in range(n):
    p.append(int(input()))
    
ans = [0 for _ in range(n + 1)]
for num in p:
    ans[num] = ans[num - 1] + 1
print(n - max(ans))

Solution (Python):
n = int(input())

count = [0]*(n+1)
P = map(int, (input() for _ in range(n)))
for p in P:
    count[p]=count[p-1]+1    

print(n - max(count))

Solution (Python):
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
chain_length = [-1 for i in range(n+1)]
for i in p:
    if chain_length[i-1] < 0:
        chain_length[i] = 1
    else:
        chain_length[i] = chain_length[i-1] + 1
print(n - max(chain_length))

Solution (Python):
n = int(input())
p = [int(input()) for _i in range(n)]

visit = [-1 for _i in range(n+1)]
for i in p:
    if visit[i-1] < 0:
        visit[i] = 1
    else:
        visit[i] = visit[i-1]+1
print(n-max(visit))

Solution (Python):
n = int(input())
p = [int(input()) for _i in range(n)]

visit = [-1 for _i in range(n+1)]
for i in p:
    if visit[i-1] < 0:
        visit[i] = 1
    else:
        visit[i] = visit[i-1]+1
print(n-max(visit))

Solution (Python):
n = int(input())
c = [int(input()) for i in range(n)]
s = [0]*n
for i,ci in enumerate(c):
  s[ci-1] = i
cnt = 1
ans = n-1
for i in range(n-1):
  if s[i] < s[i+1]:
    cnt += 1
  else:
    ans = min(n-cnt,ans)
    cnt = 1
ans = min(n-cnt,ans)
print(ans)

Solution (Python):
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)]

    p2idx = {x: i for i, x in enumerate(P)}

    
    
    max_len = 1
    tmp = 1
    for p in range(2, N + 1):
        if p2idx[p] > p2idx[p - 1]:
            tmp += 1
            if max_len < tmp:
                max_len = tmp
        else:
            tmp = 1

    print(N - max_len)

if __name__ == "__main__":
    main()

Solution (Python):
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)]

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

    print(N - max(dp))


if __name__ == "__main__":
    main()

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

dp = [0] * (n + 1)
for e in p:
    dp[e] = dp[e-1] + 1

ans = n - max(dp[1:])
print(ans)

Solution (Python):

"""
ある一要素を選んで数列の先頭もしくは最後尾に移動させる。
これを繰り返して昇順に並び替えるときの最小手数
解法：
O(N)で求める必要があるので、シュミレーション的な解法ではない。
増加部分列のうち、その増加分が1である制約を加えた場合の
部分列の長さをlとした時、
n-lが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline())-1)

lst2 = [0]*n
for i in range(n):
    lst2[lst1[i]] = i 






ans = 0
res = 1
for i in range(1,n):
    if lst2[i] > lst2[i-1]:
        res += 1
    else:
        ans = max(ans,res)
        res = 1

ans = max(ans,res)
print(n-ans)

Solution (Python):

"""
ある一要素を選んで数列の先頭もしくは最後尾に移動させる。
これを繰り返して昇順に並び替えるときの最小手数
解法：
O(N)で求める必要があるので、シュミレーション的な解法ではない。
増加部分列のうち、その増加分が1である制約を加えた場合の
部分列の長さをlとした時、
n-lが答え。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
for i in range(n):
    lst1.append(int(readline())-1)

lst2 = [0]*n
for i in range(n):
    lst2[lst1[i]] = i



ans = 0
res = 1
for i in range(1,n):
    if lst2[i] > lst2[i-1]:
        res += 1
    else:
        ans = max(ans,res)
        res = 1

ans = max(ans,res)
print(n-ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
l=[0]*N
for i in range(N):
    n=int(input())-1
    l[n]=i
a=0
t=1
for i in range(N-1):
    if l[i]<l[i+1]:
        t+=1
    else:
        if a<t:
            a=t
        t=1
if a<t:
    a=t
print(N-a)

Solution (Python):
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, -1))

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)

Solution (Python):
n = int(input())
cn = [0 for i in range(n+1)]
for i in range(n):
    p = int(input())
    cn[p] = cn[p-1]+1

print(n-max(cn))

Solution (Python):
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]
ans = N-cnt
if N ==1:
  ans = 0    
print(ans)

Solution (Python):

N=int(input())
lists=[]
for _ in range(N):
    x=int(input())
    lists.append((_,x))
lists.sort(key=lambda x:x[1])
lists.append((-10000000000000000,"end"))

cnt=0
now=-1
maxi=0
for i in range(N+1):
    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)

Solution (Python):

N=int(input())
lists=[]
for _ in range(N):
    x=int(input())
    lists.append((_,x))
lists.sort(key=lambda x:x[1])
lists.append((-10000000000000000,"end"))

cnt=0
now=-1
maxi=0
for i in range(N+1):
    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)

Solution (Python):
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
tmp = 1
for i in range(1,N):
    if Q[i] > Q[i-1]:
        tmp += 1
        x = max(x, tmp)
    else:
        tmp = 1

print(N-x)

Solution (Python):
N=int(input())
P=[]
for i in range(N):
    p=int(input())
    P.append(p)
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]<Q[i+1]:
        cnt+=1
    else:
        cnt=1
    ans=max(cnt,ans)

print(N-ans)

Solution (Python):
n = int(input())
p = [int(input()) for i in range(n)]
index = [None]*(n+1)
for i in range(n):
    index[p[i]] = i
length = 0
now = 0
max_length = 0
for i in range(1, n+1):
    if index[i] >= now:
        now = index[i]
        length += 1
    else:
        now = index[i]
        max_length = max(max_length, length)
        length = 1
max_length = max(max_length, length)

print(n-max_length)

Solution (Python):



n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = num-1

seen = [False] * n
counts =[1] * n
for num in a:
    seen[num] = True
    if num>=1 and seen[num-1]:
        counts[num] = counts[num-1] + 1
print(n - max(counts))

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))



n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = num-1

seen = [False] * n
counts =[1] * n
for num in a:
    seen[num] = True
    if num>=1 and seen[num-1]:
        counts[num] = counts[num-1] + 1
print(n - max(counts))

Solution (Python):
n=int(input())
p=[int(input())-1 for _ in range(n)]
ans=[0]*n
for i in p:
  if i!=0:
    ans[i]=ans[i-1]+1
  ans[i]=max(ans[i],1)
print(n-max(ans))

Solution (Python):
from collections import Counter

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

G = [0] * (N+1)
id = 1

for i in range(N):
    if G[P[i]-1] != 0:
        G[P[i]] = G[P[i]-1]
    else:
        G[P[i]] = id
        id+=1

C = Counter(G)

m = max(C.values())

print(N - m)

Solution (Python):
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
ans = max(ans, l)
print(N-ans-1)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
n = int(input())
p = [int(input()) for _ in range(n)]
s = [0] * n
for i in range(n):
    s[p[i] - 1] = i
ans = 0
m = s[0]
c = 0
for i in s:
    if i >= m:
        c += 1
    else:
        ans = max(ans, c)
        c = 1
    m = i
ans = max(ans, c)
print(n - ans)

Solution (Python):
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
if ans < cnt:
    ans = cnt
print(n - ans)

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

dp = [0 for i in range(n+1)]

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

print(n-max(dp))

Solution (Python):



"""
例２
3 2 5 1 4 6
5と6については昇順になっているので、4,3,2,1の順で配列の先頭に移動させればよい

↑のように考えると、既に並んでいる部分以外を適切な順で動かせばよいので、既に昇順のもので一番長いものをNから引くとよい？

"""

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



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

ans = N - 1

cnt = 1

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

ans = min(ans, N - cnt)

print(ans)

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





seen=[0 for i in range(N+1)]
for i in range(N):
  
  seen[P[i]] = seen[P[i] - 1] + 1
  
print(N - max(seen))

Solution (Python):
n=int(input())
P=[int(input()) for _ in range(n)]
DP=[0]*(n+1)

for i in P:
    DP[i]=DP[i-1]+1
print(n-max(DP))

Solution (Python):
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
    ans = max(ans,tmp)
    print(n - ans)

if __name__ =='__main__':
    main()

Solution (Python):
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)

print(N-ans-1)

Solution (Python):

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


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 = 1
    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

if __name__ == '__main__':
    solve()

Solution (Python):
N=int(input())
A=[int(input()) for i in range(N)]
cnt=0
d=0
D=[-1]*(N+1)
for i in range(N):
  D[A[i]-1]=i
cnt=1
ans=0
for i in range(N):
  if D[i]<D[i+1]:
    cnt+=1
  else:
    ans=max(cnt,ans)
    cnt=1
print(N-ans)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

cnt = [0] * (N + 1)

for i in P:
    if cnt[i - 1] != 0:
        cnt[i] = cnt[i-1] + 1
        cnt[i - 1] = 0
    else:
        cnt[i] = 1

print(N - max(cnt))

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

dp = [0]*(n+1)

for i in range(n):
    dp[pi[i]] = dp[pi[i]-1] + 1
    
print(n-max(dp))

Solution (Python):
n = int(input())
P = list(int(input()) for _ in range(n))
tmp = [0]*(n+1)
for p in P:
    tmp[p] = tmp[p-1] + 1
print(n-max(tmp))

Solution (Python):
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):
    if P[i]==1:
        dp[i] = 1
    else:
        dp[i] = dp[idx[P[i]-1]]+1
    
print(N-max(dp))

Solution (Python):
import sys

N = int(sys.stdin.readline())
P = {int(sys.stdin.readline()): i for i in range(N)}
Q = [P[i] for i in range(1, N + 1)]

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

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
p=[int(input())for _ in range(n)]
num=[-1]*n
for i in range(n):
	num[p[i]-1]=i
ans=0
kari=1
for i in range(n-1):
	if num[i+1]>num[i]:
		kari+=1
	else:
		ans=max(ans,kari)
		kari=1
ans=max(ans,kari)
print(n-ans)

Solution (Python):

import sys
from collections import defaultdict

def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))


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

    
    dp = [0]*(N+1)

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def main():
    """
    n = argmax(dp)とすると、
    (n - dp[n], n]は操作を行わなくてok

    逆にそれ以外の数は1回操作する
    -> N - dp[n]
    """
    N = int(input())

    dp = defaultdict(int)

    for _ in range(N):
        p = int(input())
        dp[p] = dp[p - 1] + 1
    
    print(N - max(dp.values()))

if __name__ == "__main__":
    main()

Solution (Python):

N = int(input())
MAXN = 2 * 10 ** 5

dp = [0] * (MAXN + 1)

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

print(N - max(dp))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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 ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

Solution (Python):









n = int(input())
posi = [-1] * n  

for k in range(n):
    temp = int(input())
    posi[temp - 1] = k - 1

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

maxx = max(maxx, temp)

print(n - maxx)

Solution (Python):
def main():
    n = int(input())
    a = [-1]*(n+2)
    for i in range(1, n+1):
        x = int(input())
        a[x] = i
    x, y = 1, 1
    ans = 0
    while y < n+2:
        if a[y-1] > a[y]:
            buf = y - x
            if buf > ans:
                ans = buf
            x = y
        y += 1
    print(n - ans)

if __name__ == "__main__":
    main()

Solution (Python):
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(min(ans,n-ms))

Solution (Python):
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
ans = max(ans, cnt)
print(N - ans)