import bisect

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

dp = []
for num in a:
    pos = bisect.bisect_left(dp, num)
    if pos < len(dp):
        dp[pos] = num
    else:
        dp.append(num)

print(n - len(dp))