题解 | #合唱队#

import bisect


def lengthOfLIS(nums: [int], endOf):
    d = []  # 数组d[i]表示长度为i的最长上升子序列的末尾元素的最小值
    # d[i] 是关于 i 单调递增
    for i, num in enumerate(nums):
        if not d or num > d[-1]:
            d.append(num)
        else:
            pos = bisect.bisect_left(d, num)
            d[pos] = num  # num一定可以更新当前的d中的一个最小值，但可能会再后面找到更小的
        endOf[i] = len(d)


n = int(input())
hight = list(map(int, input().split()))
left, right = [1] * n, [1] * n
lengthOfLIS(hight, left)
lengthOfLIS(hight[::-1], right)
right = right[::-1]
max_band = max(l + r - 1 for l, r in zip(left, right))
print(n - max_band)