题解 | #合唱队#

import bisect

# 方法1：二分法
# 获取最大增长子序列
def get_max_up_sub_arr(count, arr, arr2=[]):
    """
    :param count: 合唱队一排的人数
    :param arr:这一排人中，每个人的身高
    :return: 返回 list类型， 内容是arr列表中，每个元素的递增子序列最长的长度
    """
    dp = [1] * count  # 定义一个列表，默认子序列有当前元素1，长度是传入函数的列表长度
    for idx, i in enumerate(arr):
        if idx == 0:
            arr2 = [i]
            continue
        # print('i', i, 'arr2：', arr2, 'arr[-1]', arr2[-1], sep=' ')
        elif i > arr2[-1]:  # 如果元素大于arr列表的最后一个元素，就把它插入列表末尾
            arr2.append(i)
            dp[idx] = len(arr2)  # 获取这个元素子序列的长度
        else:  # 否则，利用二分法找到比元素大的元素的位置，用新的元素替代比它大的那个元素的值，这样就能制造出一个顺序排列的子序列
            pos = bisect.bisect_left(arr2, i)  # 用bisect_left() 找到 大于等于 i 的元素的索引
            # print('pos：', pos)
            arr2[pos] = i  # 用该元素替换 该索引的元素
            dp[idx] = pos + 1  # 获取这个元素子序列的长度， 这里的加 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