题解 | #合唱队#

# 方法1：用递增子序列方法
# 获取最大增长子序列
def get_max_up_sub_arr(count, arr):
    """
    :param count: 合唱队一排的人数
    :param arr:这一排人中，每个人的身高
    :return: 返回 list类型， 内容是arr列表中，每个元素的递增子序列最长的长度
    """
    dp = [1 for _ in range(count)]  # 定义一个dp数组，来记录 arr 列表中每个元素的递增子序列长度值
    for i in range(count):
        for j in range(i):  # 以当前元素 i 为最大数，遍历出它的递增子序列
            if arr[j] < arr[i]:  # # 筛选掉比 i 元素大的左边元素
                # 找出 i 元素 的递增子序列的最大长度， 要么是它本身 dp[i] ,
                # 要么是除它本身以外递增子序列元素中最大元素的递增子序列元素的长度 + 本身长度 1 ，也就是 dp[j] + 1
                dp[i] = max(dp[i], dp[j] + 1)
    return dp


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