from bisect import bisect_left
n=int(input())
c=list(map(int,input().split()))
t=[c[0]]
for i in range(1,n):
    if c[i]>t[-1]:
        t.append(c[i])
    else:
        index=bisect_left(t,c[i])
        t[index]=c[i]
print(n-len(t))