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

import bisect

INF = 10**18
dp = [INF]*(n+1)
dp[0] = -INF

l = 0
for a in A:
    x = bisect.bisect_right(dp, a)
    dp[x] = min(dp[x], a)
    l = max(l, x)
print(n-l)