import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    tail = []
    for x in a:
        pos = bisect.bisect_left(tail, x)
        if pos == len(tail):
            tail.append(x)
        else:
            tail[pos] = x
    print(n - len(tail))

if __name__ == "__main__":
    main()