题解 | #合唱队#

import bisect
def f(l):
    lis=[1]*len(l)
    a=[l[0]]
    for i in range(1,len(l)):
        if l[i]>a[-1]:
            a.append(l[i])
            lis[i]=len(a)
        else:
            p=bisect.bisect_left(a, l[i])
            a[p]=l[i]
            lis[i]=p+1
    return lis
while True:
    try:
        n=int(input())
        s=list(map(int,input().split()))[:n]
        left=f(s)
        right=f(s[::-1])[::-1]
        c=[left[i]+right[i]-1 for i in range(len(s))]
        print(n-max(c))
    except:
        break