;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(declaim (inline bisect-left))
(defun bisect-left (target value &key (start 0) end (predicate #'<) (key #'identity))
  "TARGET := vector | function (taking an integer argument)
PREDICATE := strict order

Analogy of lower_bound of C++ or bisect_left of Python: Returns the smallest
index (or input) i that fulfills TARGET[i] >= VALUE, where '>=' is the
complement of PREDICATE. TARGET must be monotonically non-decreasing with
respect to PREDICATE. This function returns END if VALUE exceeds
TARGET[END-1]. Note that the range [START, END) is half-open. END must be
explicitly specified if TARGET is function. KEY is applied to each element of
TARGET before comparison."
  (declare (function key predicate)
           (integer start)
           ((or null integer) end))
  (macrolet
      ((body (accessor &optional declaration)
         `(progn
            (assert (<= start end))
            (if (= start end) end
                (labels
                    ((%bisect-left (left ok)
                       ;; TARGET[OK] >= VALUE always holds (assuming
                       ;; TARGET[END] = +infinity)
                       ,@(list declaration)
                       (let ((mid (ash (+ left ok) -1)))
                         (if (= mid left)
                             (if (funcall predicate (funcall key (,accessor target left)) value)
                                 ok
                                 left)
                             (if (funcall predicate (funcall key (,accessor target mid)) value)
                                 (%bisect-left mid ok)
                                 (%bisect-left left mid))))))
                  (%bisect-left start end))))))
    (etypecase target
      (vector
       (let ((end (or end (length target))))
         (body aref (declare ((integer 0 #.most-positive-fixnum) left ok)))))
      (function
       (assert end () "Requires END argument if TARGET is a function.")
       (body funcall)))))

(declaim (inline bisect-right))
(defun bisect-right (target value &key (start 0) end (predicate #'<) (key #'identity))
  "TARGET := vector | function (taking an integer argument)
PREDICATE := strict order

Analogy of upper_bound of C++ or bisect_right of Python: Returns the smallest
index (or input) i that fulfills TARGET[i] > VALUE. TARGET must be monotonically
non-decreasing with respect to PREDICATE. This function returns END if VALUE
exceeds TARGET[END-1]. Note that the range [START, END) is half-open. END must
be explicitly specified if TARGET is function. KEY is applied to each element of
TARGET before comparison."
  (declare (function key predicate)
           (integer start)
           ((or null integer) end))
  (macrolet
      ((body (accessor &optional declaration)
         `(progn
            (assert (<= start end))
            (if (= start end)
                end
                (labels
                    ((%bisect-right (left ok)
                       ;; TARGET[OK] > VALUE always holds (assuming
                       ;; TARGET[END] = +infinity)
                       ,@(list declaration)
                       (let ((mid (ash (+ left ok) -1)))
                         (if (= mid left)
                             (if (funcall predicate value (funcall key (,accessor target left)))
                                 left
                                 ok)
                             (if (funcall predicate value (funcall key (,accessor target mid)))
                                 (%bisect-right left mid)
                                 (%bisect-right mid ok))))))
                  
                  (%bisect-right start end))))))
    (etypecase target
      (vector
       (when (null end)
         (setf end (length target)))
       (body aref (declare ((integer 0 #.most-positive-fixnum) left ok))))
      (function
       (assert end () "Requires END argument if TARGET is a function.")
       (body funcall)))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((n (read))
         (as (make-array n :element-type 'uint32))
         (dp (make-array n :element-type 'int32 :initial-element -1)))
    (dotimes (i n) (setf (aref as i) (read-fixnum)))
    (dotimes (i n)
      (let* ((a (aref as i))
             (pos (bisect-right dp a :predicate #'>)))
        (setf (aref dp pos) a)))
    (println (count-if (lambda (x) (>= x 0)) dp))))

#-swank (main)


;; For Test
#+swank
(defun io-equal (in-string out-string &optional (func #'main))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNC, and returns true if the
string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (and (> (length s) 0)
                      (eql (char s (- (length s) 1)) #\Linefeed))
                 s
                 (uiop:strcat s uiop:+lf+))))
    (equal (ensure-last-lf out-string)
           (with-output-to-string (out)
             (let ((*standard-output* out))
               (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                 (funcall func)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  (let ((*standard-output* out))
    (etypecase thing
      (null ; Runs #'MAIN with the string on clipboard
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname ; Runs #'MAIN with the string in a text file
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5
2
1
4
5
3
"
    "2
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
0
0
0
0
"
    "4
")))


Measured memory_bytes: 35044