题解 | #合唱队#

# 此题的难度在于求序列中每个元素的最长递增子序列，如：
# 原序列为长度为N的序列[8,20,12,15,10,9]，
# 从左至右每个元素的最长子序列的长度分别为：l1 = [1,2,2,3,2,2]
# 从右至左每个元素的最长子序列的长度分别为：l2 = [1,4,3,3,2,1]
# 则 l1 + l2 = [2,6,5,6,4,3]，则合唱队伍最长为：l = max[l1 + l2] - 1(去掉重复的自己一次) ，
# 则最小出列人数为：N - l
# 则此题的关键在于求得l1 和 l2 。
# 用dp[i] 表示从左至右到原序列第i个元素的递增子序列的长度的值
import bisect
# 求原序列中每个元素从左至右最长递增子序列长度的方法
def mf_dp(n, sl):
    # 存放每个元素的递增子序列的长度，最小为1，即它本身
    dp = [1] * n
	# 存放递增子序列
    arr = [sl[0]]
    # 从第二个元素开始比
    for i in range(1, n):
        # 比的是递增子序列的最后一个值，因为是递增的
        if sl[i] > arr[-1]:
            arr.append(sl[i])
            # 存放当前元素的最长递增子序列的长度
            dp[i] = len(arr)
        else:
            pos = bisect.bisect_left(arr, sl[i])
            arr[pos] = sl[i]
            dp[i] = len(arr)
    return dp


while True:
    try:
        n = int(input())
        sl = list(map(int, input().split()))
        l1 = mf_dp(n, sl)               # 从左至右
        l2 = mf_dp(n, sl[::-1])[::-1]   # 从右至左
        l = [l1[i] + l2[i] - 1 for i in range(n)]
        print(str(n - max(l)))
    except:
        break