题解 | #合唱队#

import bisect

# 方法2：二分法
# 获取最大增长子序列
def get_max_up_sub_arr(count, arr, arr2=[]):
    """
    :param count: 合唱队一排的人数
    :param arr:这一排人中，每个人的身高
    :return: 返回 list类型， 内容是arr列表中，每个元素的递增子序列最长的长度
    """
	# 首先，我们定义了变量 count 和列表 arr，它们包含了我们要处理的数据。
	#然后，我们使用列表推导式创建了变量 dp，它存储了最长递增子序列的长度。
	#在列表推导式中，我们迭代 arr 列表的每个元素，并使用条件表达式判断元素应该放在新的子序列中还是替换已有子序列中的元素。
	# 对于大于已有子序列的元素，我们将其追加到 arr2 列表中，并更新 dp 的对应位置为 len(arr2)。
	# 对于小于或等于已有子序列的元素，我们使用二分查找找到应该插入的位置 pos，并使用 arr2.__setitem__(pos, i) 将元素 i 替换到 arr2 中的对应位置。
	# 最后，return出 dp 列表和其长度列表。
    arr2 = [arr[0]]
    return [
        len(arr2 := arr2 + [i])
        if i > arr2[-1]
        else (arr2.__setitem__(pos := bisect.bisect_left(arr2, i), i), pos + 1)[1]
        for i in arr
    ]
 
while True:
    try:
        count = int(input())  # 输入合唱队一排人数
        arr = list(map(int, input().split(" ")))  # 输入这一排每个人的身高
        left_up_arr = get_max_up_sub_arr(count, arr)  # 从左到右 遍历每个元素的递增子序列
        right_up_arr = get_max_up_sub_arr(count, arr[::-1])[::-1]  # 从右到左 遍历每个元素的递增子序列
        # 用 zip() 将left_up_arr, right_up_arr 两个列表打包合并
        # print("zip()：", list(zip(left_up_arr, right_up_arr)))
        # i + j - 1 , i + j 就是将每个元素的 左边和右边的递增子序列长度相加，因为重复加了本身长度2次， 所以要减 1
        # max(i + j - 1 for i, j in zip(left_up_arr, right_up_arr)) 分别获取 每个元素的左边和右边的递增子序列的长度，并获取最长的递增子序列
        # count - 最长递增子序列  就得到最少需要几位同学出列
        print(count - max(i + j - 1 for i, j in zip(left_up_arr, right_up_arr)))
    except EOFError:
        break