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

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

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

Solution (Python):
def main():
    n = int(input())
    dp = [-1 for _ in range(n)]
    for _ in range(n):
        x = int(input()) - 1
        if x > 0 and dp[x - 1] != -1:
            dp[x] = dp[x - 1] + 1
        else:
            dp[x] = 1
    print(n - max(dp))

main()

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

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

print(N-max(dp))

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



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

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

Solution (Python):
def solve(N, P):
    xs = [0] * N
    for i, x in enumerate(P):
        xs[x - 1] = i
    r = 0
    c = 0
    p = -1
    for i, x in enumerate(xs):
        if p < x:
            c += 1
            r = max(r, c)
        else:
            c = 1
        p = x
    return N - r

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

print(solve(N, P))

Solution (Python):
N = int(input())
src = [int(input())-1 for i in range(N)]
ids = [None] * N
for i,a in enumerate(src):
    ids[a] = i

longest = seq = 1
for i1,i2 in zip(ids, ids[1:]):
    if i1 < i2:
        seq += 1
    else:
        longest = max(longest, seq)
        seq = 1
longest = max(longest, seq)
print(N - longest)

Solution (Python):

import numpy as np

n = int(raw_input())

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

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

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







ans = n-np.max(count)

print ans

Solution (Python):

N = int(input())
cache = dict()
for i in range(1, N+1):
    p = int(input())
    cache[p] = cache.get(p-1, 0) + 1
print(N-max(cache.values()))

Solution (Python):


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

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

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

longest = 1
current = 1

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

if current > longest:
    longest = current

print(n - longest)

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

print(n - Max)

Solution (Python):


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

    xx = [-1] * n
    for s in range(n - 1, -1, -1):
        if xx[s] >= 0:
            continue
        count = 1
        pre = pp[s]
        while pre + 1 in dd and dd[pre + 1] > s:
            i = dd[pre + 1]
            if xx[i] >= 0:
                xx[s] = xx[i] + count
                break
            pre += 1
            count += 1
        else:
            xx[s] = count
    print(n - max(xx))


if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy
import itertools


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


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


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


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

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

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

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

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


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

Solution (Python):




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

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

    print(N - max_)


if __name__ == '__main__':
    main()

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

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq






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

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

    return n-ma


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

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

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

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

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

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

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

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

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

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

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

N = read()

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

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

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

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

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

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

import itertools

P = nAuto(nAuto())

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

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

print(len(P) - mn)

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

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

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








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

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

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

Solution (Python):

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

Solution (Python):



import sys

input=sys.stdin.readline

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

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

print(n-max(got))