题解 | #合唱队#

# 输入同学的总数和身高
N = int(input())
heights = list(map(int, input().split()))

# 这里是最长递增子序列的二分法判断
def getPos(value, B_list):
    left = 0
    right = len(B_list)-1
    while left <= right:
        mid = int((left + right) // 2)
        if B_list[mid] > value:
            right = mid - 1
        elif B_list[mid] < value:
            left = mid + 1
        else:
            return mid
    return left

B_list = [heights[0]]  # 记录从左侧开始的最长子序列记录
dp = [0 for i in range(N)]  # 用来存放当第i位同学左侧的最长子序列的长度

# 遍历所有同学信息
for i in range(1,N):
    # 当 i同学身高大于最长序列的最高值时，B序列新增一个元素，此时i同学左侧的最长子序列长度为B_list的长度-1
    if heights[i]>B_list[-1]:
        B_list.append(heights[i])
        dp[i] = len(B_list)-1
    else: 
        # 否则 就需要判断，该同学能够拍到左边序列的哪个位置，比如 返回的位置为2,那么就说明i同学左侧最长递增子学列的长度为2，所以直接赋值
        pos = getPos(heights[i],B_list)
        B_list[pos] = heights[i]
        dp[i] = pos

# 下述同理，把右侧的最长递减子序列获取得到，（或者直接列表倒叙，逻辑不变，只需要列表倒叙两次），查询到i同学右侧的最长递减子序列长度。
dp2 = [0 for i in range(N)]
temp_list = heights[::-1]
d_list = [temp_list[0]]
for i in range(1, N):
    # print(i)
    if temp_list[i]>d_list[-1]:
        d_list.append(temp_list[i])
        dp2[i] = len(d_list)-1
    else:
        # print(i,d_list)
        pos = getPos(temp_list[i],d_list)
        d_list[pos] = temp_list[i]
        dp2[i] = pos

# 再次遍历，查询i同学的左侧和右侧相应得最长递增递减子序列长度
max_len = 0
for i in range(N):
    if dp[i] + dp2[::-1][i] > max_len:
        max_len = dp[i] + dp2[::-1][i] 
        
# 最后输出，因为max_len 没有加上中心自身，所以真实最长应该时（max_len+1）,需要剔除就如输出
print(N-max_len-1)