题解 | #合唱队#

import bisect  # 导入 bisect 模块，用于操作有序列表

def max_order(lists):
    list_num = []  # 用于保存当前的递增序列
    list_max = []  # 用于保存每个位置上最长递增子序列的长度

    # 遍历输入列表中的每个元素
    for i in lists:
        # 使用 bisect_left 在 list_num 中找到 i 应该插入的位置
        local = bisect.bisect_left(list_num, i)

        # 如果 local 等于 list_num 的长度
        if local == len(list_num):
            # 说明 i 大于 list_num 中所有元素，将 i 添加到 list_num 的末尾
            list_num.append(i)
            # 在 list_max 中添加 local + 1，表示以 i 结尾的最长递增子序列的长度
            list_max.append(local + 1)
        else:
            # 否则，local 是 list_num 中第一个不小于 i 的位置，替换该位置的元素为 i
            list_num[local] = i
            # 在 list_max 中添加 local + 1，保持了 list_num 的有序性
            list_max.append(local + 1)

    # 返回每个位置上最长递增子序列的长度
    return list_max

# 主程序循环，持续读取输入，直到发生异常（例如 EOF 或输入不合法）
while True:
    try:
        # 读取总人数
        people_num = int(input())
        # 读取并解析身高列表
        height_list = list(map(int, input().split()))

        # 计算正向最长递增子序列的长度
        result_1 = max_order(height_list)
        # 计算逆向最长递增子序列的长度，然后再逆序（即正向最长递减子序列的长度）
        result_2 = max_order(height_list[::-1])[::-1]

        # 使用 zip 将 result_1 和 result_2 对应位置元素相加，计算每个位置的合唱队形长度
        # max(map(sum, zip(result_1, result_2))) 找到最长的合唱队形长度
        # people_num - max(...) + 1 计算最少需要移除的同学数量
        print(people_num - max(map(sum, zip(result_1, result_2))) + 1)
    except BaseException as er:
        # 如果发生任何异常（如 EOF 或输入不合法），程序将中止
        break