题解 | #合唱队#

N = int(input())
a = list(map(int, input().split()))

ans = 0
lf = [1] * (N)
rf = [1] * (N)
# for i in range(1, N):
#     for j in range(i):
#         if a[j] < a[i]:
#             lf[i] = max(lf[i], lf[j]+1)

# for i in range(N-2, -1, -1):
#     for j in range(N-1, i, -1):
#         if a[j] < a[i]:
#             rf[i] = max(rf[i], rf[j]+1)
# TLE

import bisect

lf = [1000000 for _ in range(N)] # 维护最有递增潜力子列
rf = [1000000 for _ in range(N)]
lcnt = [1] # lcnt[i] = n : 第i个人作为中间时, 它左边最多能站几个人构成递增子列
rcnt = [1] 

lf[0] = a[0]
for i in range(1, N):
    idx = bisect.bisect_right(lf, a[i]) # 这个是<= 需要手动去除=
    if idx > 0 and lf[idx-1] == a[i]:
        lcnt.append(idx)    # 两个人身高一样, 则它们左边站的人数也一样
    else:
        lf[idx] = a[i]
        lcnt.append(idx+1)

rf[0] = a[-1]
for i in range(N-2, -1, -1):
    idx = bisect.bisect_right(rf, a[i])
    if idx > 0 and rf[idx-1] == a[i]:
        rcnt.append(idx)
    else:
        rf[idx] = a[i]
        rcnt.append(idx+1)
rcnt.reverse()

for l, r in zip(lcnt, rcnt):
    ans = max(ans, l+r)

print(N-ans+1)

# ps: 会有人身高超过十米?