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())
P=[None]*N
for i in range(N):
    P[i]=int(input())


r=1
l=N
rcount=0
lcount=0
for i in range(N):
    if P[i]==r:
        r+=1
        rcount+=1

for i in range(N-1,-1,-1):
    if P[i]==l:
        l-=1
        lcount+=1

Ans=N-max(rcount,lcount)

print(Ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
checkf = 1
checkl = N
countf = 0
countl = 0
for i in range(N):
    if P[i] == checkf:
        countf += 1
        checkf += 1
    if P[N-1-i] == checkl:
        countl += 1
        checkl -= 1

print(N-max(countf, countl))

Submission status: Wrong Answer

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

reversed_P = P[:]
reversed_P.reverse()
counter = 0
biggest = N

for i in reversed_P:
    if i == biggest:
        counter += 1
        biggest -= 1

print(N - counter)

Submission status: Wrong Answer

Solution code:
n = int(input())

c = 0
t = n + 1
for i in range(n):
  s = int(input())
  if(s == 1 or s > t):
    c += 1
    t = s

print(n - c + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def longest_increasing_subsequence(X):
    """Returns the Longest Increasing Subsequence in the Given List/Array"""
    N = len(X)
    P = [0] * N
    M = [0] * (N+1)
    L = 0
    for i in range(N):
        lo = 1
        hi = L
        while lo <= hi:
            mid = (lo+hi)//2
            if (X[M[mid]] < X[i]):
                lo = mid+1
            else:
                hi = mid-1

        newL = lo
        P[i] = M[newL-1]
        M[newL] = i

        if (newL > L):
            L = newL

    S = []
    k = M[L]
    for i in range(L-1, -1, -1):
        S.append(X[k])
        k = P[k]
    return len(S[::-1])

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

    return n-longest_increasing_subsequence(a)+1


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 #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
#! -*- coding: utf-8 -*-
import numpy as np

n = int(raw_input())

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


check = 1
for i in range(n):
    if p[i] == check:
        check += 1

checkinv = n
i = n-1
while i >= 0:
    if p[i] == checkinv:
        checkinv-=1
    i -= 1

#print check-1,n-checkinv

#print n-(check-1),checkinv

ans = min(n-(check-1),checkinv)

print ans

Submission status: Wrong Answer

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

now_pos = 0
count_1 = 0
for j in range(N):
    pos_new = P.index(j+1)
    if pos_new >= now_pos:
        count_1 += 1
        now_pos = pos_new
    else:
        break;

now_pos = N-1
count_2 = 0
for j in range(N):
    pos_new = P.index(N-j)
    if pos_new <= now_pos:
        count_2 += 1
        now_pos = pos_new
    else:
        break;

count = max(count_1, count_2)

print(N - count)

Submission status: Wrong Answer

Solution code:
N = int(input())

max_int = 0
ans = 0
for i in range(N):
    n = int(input())
    if n > max_int:
        max_int = n
    else:
        ans = n
        
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = [int(input()) for _ in range(n)]
p, q = 0, 0
s, t = min(nums), max(nums)

for i in range(n):
    if nums[i] == s + 1:
        p += 1
        s = nums[i]
    if nums[n-i-1] == t - 1:
        q += 1
        t = nums[n-i-1]
ans = n - max(p, q) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = []
for i in range(n):lis.append(int(input()))
co = 0
cou = n-2
for i in range(1,n):
    if lis[i]-lis[i-1] == 1:
        cou -= 1
print(cou)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = []
for i in range(N):
    P.append(int(input()))
t1,step1 = 1,0
for i in range(N):
    if P[i]==t1:
        t1 += 1
        continue
    step1 += 1
t2,step2 = N,0
for i in range(N):
    if P[N-1-i]==t2:
        t2 -= 1
        continue
    step2 += 1
print(min(step1,step2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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

    ans = float('inf')
    cur = 1
    for i in xrange(n):
        if a[i] == cur:
            cur += 1

    ans = min(ans, n-cur+1)

    cur = n
    for i in xrange(n-1,-1,-1):
        if a[i] == cur:
            cur -= 1

    ans = min(ans, cur)

    return ans


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 #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

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

i = 1
cnt_f = 0
for p in ppp:
    if p == i:
        cnt_f += 1
        i += 1

i = n
cnt_b = 0
for p in ppp[::-1]:
    if p == i:
        cnt_b += 1
        i -= 1

cnt = max(cnt_f, cnt_b)
print(n - cnt)

Submission status: Wrong Answer

Solution code:
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 = 0
for i in range(N-1):
    if Q[i] < Q[i+1]:
        cur += 1
    else:
        cur = 1
    ans = max(cur, ans)
print(N - ans)

Submission status: Wrong Answer

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

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

j = N
for k in reversed(range(N)):
    if P[k] == j:
        j -= 1

print(min(N - i + 1, j))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = [[int(input()),1]]
cou = 1
for i in range(n-1):
    now = int(input())
    flag = False
    for i in range(cou):
        if now == k[i][0] + 1:
            k[i] = [now,k[i][1]+1]
            flag = True
    if not flag:
        k.append([now,1])
        cou += 1
p = 0
for i in range(cou):
    p = max(p,k[i][1])
print(n-p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = [[int(input())]]
cou = 1
for i in range(n-1):
    now = int(input())
    flag = False
    for i in range(cou):
        if now == k[i][-1]+1:
            k[i].append(now)
            flag = True
    if not flag:
        k.append([now])
        cou += 1
p = 0
for i in range(cou):
    p = max(p,len(k[i]))
print(n-p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
bbr = []
bbr.append([1,int(input())])
for i in range(n-1):
    p = int(input())
    for j in range(n):
        if bbr[j][1]+1 == p:
            bbr[j][1] += 1
            bbr[j][0] += 1
            break
        if j == len(bbr)-1:
            bbr.append([1,p])
            break

bbr.sort(reverse=True)
print(n-bbr[0][0])

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline())
P = [int(sys.stdin.readline()) for _ in range(N)]
Q = [P.index(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)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(input()) for i in range(N)]
ans = 0
for i in range(N):
    nowc = 1
    now = P[i]
    for j in range(i+1,N):
        if P[j] == now+1:
            nowc += 1
            now += 1
    ans = max(ans,nowc)
print(N-ans)

Submission status: Time Limit Exceeded

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
k = 1
for i in range(n-1):
    tmp = 1
    j = i
    while j < n-1 and q[j] < q[j+1]:
        j += 1
        tmp += 1
    k = max(k, tmp)
print(n-k)

Submission status: Time Limit Exceeded

Solution code:
#N, *a = map(int, open(0).read().split())
def main():
    N = int(input())
    a=[]
    for i in range(N):
        a.append(int(input()))

    b = [1 for _ in range(N+1)]
    cnt = 1
    ans = 0
    flag = 1
    i = 0
    for i in reversed(range(N)):
        if a[i] + 1 in a[i:]:
            b[a[i]] = b[a[i]+1] + 1
        
        
    return N-max(b)
print(main())

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
data=[int(input()) for i in range(N)]
mae=N//2+N%2
i=1
count=0

maelist=[]
maeset=set()
usirolist=[]
usiroset=set()
flag=1
lst=set()
nikaime=0
dellst=set()
while flag:
    flag=0
    if lst:
        lst.clear()
    for i in range(len(data)):
        if data[i] in dellst:
            dellst.remove(data[i])
            data[i]=0
            continue
        lst.add(data[i])
        if data[i]+1 in lst or data[i]+1 in maeset:
            flag=2
            count+=1
            if data[i]<=mae:
                maelist.append(data[i])
                maeset.add(data[i])

                data[i]=0


            else:
                usirolist.append(data[i]+1)
                usiroset.add(data[i]+1)
                dellst.add(data[i]+1)

    for i in usirolist:
        if i+1 in set(data):
            dellst.add(i+1)
            usirolist.append(i+1)
            count+=1
            flag=1

    if flag:
        data=[i for i in data if i]
    if not nikaime:
        nikaime=1

maelist.reverse()
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
data=deque([int(input()) for i in range(N)])
mae=N//2+N%2
i=1
count=0

while i<N:
    data2=list(data)
    #print(data)
    if (data[i]+1) in data2[:i]:
        #print("unko",i)
        t=data[i]
        if t<=mae:

            data.remove(t)
            data.appendleft(t)
            count+=1
        else:
            t+=1
            data.remove(t)
            data.append(t)
            count+=1
        i=0
    i+=1

#print(data)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

mx = 0
for i in range(1, N+1):
    cnt = 0
    nxt = i
    for a in A:
        if a == nxt:
            cnt += 1
            nxt += 1
    mx = max(mx, cnt)
print(N - mx)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(input()) for _ in range(N)]
maxlen = 1
tmplen = 1
indexls = [P.index(i+1) for i in range(N)]
for i in range(1,N):
    if indexls[i] > indexls[i-1]:
        tmplen += 1
        maxlen = max(maxlen,tmplen)
    else:
        tmplen = 1
print(N-maxlen)

Submission status: Time Limit Exceeded

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

seen = [0] * (n + 1)
i = 0
counter = 0
while i < n:
    if seen[i]:
        i += 1
        continue

    p = P[i]
    seen[i] = 1
    cnt = 1
    for j in range(i+1, n):
        if P[j] == p + 1:
            seen[j] = 1
            cnt += 1
            p += 1
    i += 1
    counter = max(counter, cnt)

ans = n - counter
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = []
    for i in range(N):
        ind.append(A.index(i+1))
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ind = []
    for i in range(N):
        ind.append(A.index(i+1))
    
    ind.reverse()
    for i in range(N-1):
        if ind[i] < ind[i+1]:
            print(N-i-1)
            exit()

    print(0)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    P = [0] * N

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

    dp = [(0, 0)]

    for p in P:
        i = bisect_right(dp, (p, INF))
        if dp[i - 1][0] == p - 1:
            dp[i - 1] = (p, dp[i - 1][1] + 1)
        else:
            dp.insert(i, (p, 1))

    length = 1
    for _, l in dp:
        length = max(length, l)

    print(N - length)

sol()

Submission status: Time Limit Exceeded

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

a = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for x in p:
    a[x][x] = 1
    for i in range(1, x):
        if a[i][x - 1] == 1:
            a[i][x] = 1

ans = 0
for i in range(1, n + 1):
    ans = max(ans, sum(a[i]))

print(n - ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin, stdout

rem=10**9+7
sys.setrecursionlimit(10 ** 6)
take = lambda: map(int, stdin.readline().split())

n=input()
ans=[1 for i in range(n+1)]
pos={}
for i in range(1,n+1):
    x=input()
    pos[x]=i
for i in range(n-1,0,-1):
    if pos[i]<pos[i+1]:
        ans[i]=ans[i+1]+1
#print(ans)
print n-max(ans)

Submission status: Time Limit Exceeded

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

indeces = [0] * n

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

ans = 0

for i in range(n):
	j = i
	front = 0
	while True:
		if j == n - 1:
			break
		elif indeces[j] < indeces[j + 1]:
			front += 1
			j += 1
		else:
			break
	if front > ans:
		ans = front

print(n - ans - 1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=[]
for i in range (n):
	p.append(int(input()))
pos=0
num=0
n_th = 0
for i in range(n):
	if i+1 in p[pos:]:
		num += 1
		pos = p[pos:].index(i+1)+pos
	else:
		if num>n_th:
			n_th = num
		if i+1 in p:
			num = 1
			pos = p.index(i+1)
if num >n_th:
	print (n-num)
else:
	print(n-n_th)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
from itertools import chain

def gen_check_numbers(n):
    center = n // 2
    l2 = chain.from_iterable(zip(reversed(range(1, center + 1)), range(center + 1 , n + 1)))
    return l2

def main():
    n = int(input())
    l = [ int(input().rstrip()) for i in range(n)]

    ans = 0
    center = n // 2
    for i in gen_check_numbers(n):
        i1 = l.index(i)
        if i <= center:
            i2 = l.index(i + 1)
            if( i2 < i1):
                l.remove(i)
                l.insert(0,i)
                ans += 1
        else:
            i2 = l.index(i - 1)
            if( i1 < i2):
                l.remove(i)
                l.append(i)
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
groups = []
for i in range(N):
  p = int(input())
  b = False
  for g in groups:
    if g[len(g) - 1] == p - 1:
      g.append(p)
      b = True
      break
  if not b:
    groups.append([p])
lengths = list(map(len, groups))
print(N - max(lengths))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
res = 0
for _ in range(N):
  a.append(int(input()))

hasGreaterBefore = set()
max_v, min_v = 0, 2e5

for e in a:
    if max_v < e:
        max_v = e
    else:
        hasGreaterBefore.add(e)

for num in range(N, 0, -1):
    if num in hasGreaterBefore:
        eidx = a.index(num)
        hasGreaterBefore.remove(num)
        if num > a[0]:
            hasGreaterBefore.add(a[0])
        if eidx != 0:
            a.pop(eidx)
            a = [num] + a
            res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
res = 0
for _ in range(N):
  a.append(int(input()))

hasGreaterBefore = set()

for num in range(N, 0, -1):
    max_v, min_v = 0, 1e5
    hasGreaterBefore.clear()
    for e in a:
        if max_v < e:
            max_v = e
        else:
            hasGreaterBefore.add(e)

    if num in hasGreaterBefore:
        eidx = a.index(num)
        if eidx != 0:
            a.pop(eidx)
            a = [num] + a
            res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
n = int(input())
l = [ int(input()) for i in range(n)]
ans = tuple(sorted(l))

checked = set()

s = [(l, 0)]
for loop_count in count():
    #print(loop_count, len(s), len(checked))
    #print(s, checked)
    tl, ns = s.pop(0)
    if tuple(tl) in checked:
        continue
    if ans == tuple(tl):
        print(ns)
        break
    for i in range(n):
        n1 = list(tl)
        c = n1.pop(i)
        n1.append(c)
        if(tuple(n1) not in checked):
            s.append((n1, ns+1))
        n2 = list(tl)
        c = n2.pop(i)
        n2.insert(0, c)
        if(tuple(n2) not in checked):
            s.append((n2, ns+1))
    checked.add(tuple(tl))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

dic = {p[0]:1}
for i in range(1,n):
    #print(dic)
    check = 0
    for k in list(dic):
        #print(k, dic[k])
        if p[i] == k + dic[k]:
            dic[k] += 1
            check = 1
            break
        elif p[i] == k - 1:
            dic[p[i]] = 1
            if dic[k] < max(dic.values()):
                dic.pop(k)
        else:
            dic[p[i]] = 1

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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


# 連続している最大値を求める

max_count = 0
for starti in range(len(p)):
    previous = p[starti]
    count = 1
    for i in range(starti, len(p)):
        if previous + 1 == p[i]:
            previous += 1
            count += 1

    if max_count < count:
        max_count = count

    
print(n-max_count)

Submission status: Time Limit Exceeded

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

q_dict = {0:0}
for p in p_list:
    q_dict[p] = p_list.index(p)
length = 0
ans = 1
for i in range(1, n+1):
    if q_dict[i] > q_dict[i-1]:
        length += 1
        if length > ans:
            ans = length
    else:
        length = 1
print(n - ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = []
for i in range(n):
    p.append(int(input()))
place = []
for i in range(n):
    place.append(p.index(i + 1))

length = 1
sequence = []
for i in range(n - 1):
    if place[i] < place[i + 1]:
        length = length + 1
    else:
        sequence.append(length)
        length = 1
sequence.append(length)
print(n - max(sequence))

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
p=[]
for i in range(n):   
 p.append(i1())

s=0
while p[0]!=1 or p[-1]!=n:
 j=0
 if p[0]==1 and p[-1]!=n:
   k=p[-1]
   s+=n-p[-1]
   while len(p)>j:
       if p[j]>k:
         p.pop(j)
         j-=1
       j+=1
   p=p+list(range(k+1,n+1))
 if p[0]!=1 and  p[-1]==n:
   k=p[0]
   s+=p[0]-1
   while len(p)>j:
       if p[j]<k:
          p.pop(j)
          j-=1
       j+=1
   p=list(range(1,k))+p
 if p[0]!=1 and  p[-1]!=n:

  if n-p[-1]>p[0]-1:
   k=p[0]
   s+=p[0]-1
   while len(p)>j:
       if p[j]<k:
          p.pop(j)
          j-=1
       j+=1
   p=list(range(1,k))+p
  else:
   k=p[-1]
   s+=n-p[-1]
   while len(p)>j:
       if p[j]>k:
         p.pop(j)
         j-=1
       j+=1
   p=p+list(range(k+1,n+1))
j=0

while n-1>j:
   if p[j]>p[j+1]:
     s+=1
     if p[j+1]-1<n-p[j]:
        p.insert(0,p[j+1])
        p.pop(j+2)
        j+=1
     else:
        p.append(p[j])
        p.pop(j)
   else:
        j+=1
print(s)

Submission status: Time Limit Exceeded

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

length = 1
sequence = []
for i in range(n - 1):
    if p.index(i + 1) < p.index(i + 2):
        length = length + 1
    else:
        sequence.append(length)
        length = 1
sequence.append(length)
print(n - max(sequence))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
p = deque()
for _ in range(n):
    p.append(int(input()))
i = 0
ans = 0
while i < n - 1:
    if p[i] >= int(n/2) and p[i] > p[i+1]:
        temp = p[i]
        del p[i]
        p.append(temp)
        ans += 1
    else:
        i += 1
i = 0
while i < n - 1:
    if p[i] < int(n/2) and p[i] > p[i+1]:
        temp = p[i+1]
        del p[i+1]
        p.appendleft(temp)
        ans += 1
    else:
        i += 1
print(ans)

Submission status: Time Limit Exceeded

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

start = 1
length = 1
sequence = []
for i in range(n - 1):
    if p.index(i + 1) < p.index(i + 2):
        length = length + 1
    else:
        sequence.append(length)
        start = i + 2
        length = 1
sequence.append(length)
print(n - max(sequence))

Submission status: Time Limit Exceeded

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

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

    print(N-asc_num)



if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

visited = [0 for i in range(n)]
n_range = range(n)
for i in reversed(n_range):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1
        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
print(n - max(visited))

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

a=[0]*n
kai1 = n -1
kai2 = n -1
for i in range(n):
#    print(t.index(i+1))
    a[i]=t.index(i+1)
#print(a)
for j in range(1,n,1):
    if a[j-1] < a[j]:
        kai1 -= 1
    else:
        break
    #
for j in range(n,0,-1):
    if a[j-1] > a[j-2]:
        kai2 -= 1
    else:
        break

#print(kai1,kai2)

print(min(kai1,kai2))

Submission status: Time Limit Exceeded

Solution code:

num=input()
num=int(num)

list1=[]
list2=[]
for i in range(num):
    n=input()
    n=int(n)
    list1.append(n)
    list2.append(n)
    
count=0
for j in range(num):
    for k in range(list1.index(num-j)+1):
        if list1[k]>list1[list1.index(num-j)]:
            #print(str(list1[list1.index(num-j)])+" "+str(k))
            del list1[list1.index(num-j)]
            list1.insert(0,num-j)
            #print(list1)
            count=count+1
            break
        else:
            k+=1
#print(count)

count2=0
for j in range(1,num+1):
    for k in range(list2.index(j),num):
        if list2[k]<list2[list2.index(j)]:
            #print(str(list1[list1.index(j)])+" "+str(k))
            del list2[list2.index(j)]
            list2.insert(num-1,j)
            #print(list2)
            count2=count2+1
            break
        else:
            k+=1
#print(count2)
if count<=count2:
    print(count)
else:
    print(count2)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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


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

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

count = 0

center = ordered[len(ordered)//2]
unordered.sort(key=(lambda x: abs(x - center)))

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


    ordered.insert(index, t)

print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

min = 1
max = n
c_p_max = sorted(p)
c_p_min = copy.copy(c_p_max)
min_p =copy.copy(p)
max_p = copy.copy(p)

while min_p != c_p_min:
    min_p.remove(min)
    c_p_min.remove(min)
    min_k += 1
    min += 1

while max_p != c_p_max:
    max_p.remove(max)
    c_p_max.remove(max)
    max_k += 1
    max -= 1
ans = [min_k,max_k]
ans.sort()
print(ans[0])

Submission status: Time Limit Exceeded

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

visited = [0 for i in range(n)]

for i in reversed(range(n)):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1
        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
print(n - max(visited))