题解 | #合唱队# 二分查找 O(nlogn)

import bisect

n = int(input())

a = list(map(int, input().split()))
lt = [0] * n
rt = [0] * n

st = []  # st[i]表示 所有递增子序列，可以排第i位同学的最低身高；可以证明st自身也是是递增的
for i in range(n):
    idx = bisect.bisect_left(st, a[i])
    if idx == len(st):
        st.append(a[i])
    st[idx] = a[i]   # 更新可以排第i位同学的最低身高
    lt[i] = i - idx

st = []
for i in range(n - 1, -1, -1):
    idx = bisect.bisect_left(st, a[i])
    if idx == len(st):
        st.append(a[i])
    st[idx] = a[i]
    rt[i] = n - 1 - i - idx
ans = 3000
for i in range(n):
    ans = min(ans, lt[i] + rt[i])
print(ans)