题解 | #合唱队#

import bisect


def GetDP(ls):
    dp = [1 for _ in range(len(ls))]
    arr = [ls[0]]
    for i in range(1, len(ls)):
        if ls[i] > arr[-1]:
            arr.append(ls[i])
            dp[i] = len(arr)
        else:
            pos = bisect.bisect_left(arr, ls[i])
            arr[pos] = ls[i]
            dp[i] = pos + 1
    return dp


N = int(input())
ls = list(map(int, input().split()))
dp1 = GetDP(ls)
dp2 = GetDP(ls[::-1])[::-1]
dp = [dp1[i] + dp2[i] - 1 for i in range(N)]
print(N - max(dp))