;; -*- 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 (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
;; Not included in test script. Better to use ref-able-treap instead.
(defstruct (treap (:constructor make-treap (key priority &optional left right))
                  (:copier nil)
                  (:conc-name %treap-))
  (key 0 :type fixnum)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null treap))
  (right nil :type (or null treap)))

(declaim (inline treap-find))
(defun treap-find (key treap &key (test #'<))
  "Searches the sub-treap of TREAP whose key satisfies (and (not (funcall test
key (%treap-key sub-treap))) (not (funcall test (%treap-key sub-treap) key))) and
returns KEY. Returns NIL if KEY is not contained."
  (declare (function test)
           ((or null treap) treap))
  (labels ((recur (treap)
             (cond ((null treap) nil)
                   ((funcall test key (%treap-key treap))
                    (recur (%treap-left treap)))
                   ((funcall test (%treap-key treap) key)
                    (recur (%treap-right treap)))
                   (t key))))
    (recur treap)))

(declaim (inline treap-split))
(defun treap-split (key treap &key (test #'<))
  "Destructively splits the TREAP with reference to KEY and returns two treaps,
the smaller sub-treap (< KEY) and the larger one (>= KEY)."
  (declare (function test)
           ((or null treap) treap))
  (labels ((recur (treap)
             (cond ((null treap)
                    (values nil nil))
                   ((funcall test (%treap-key treap) key)
                    (multiple-value-bind (left right)
                        (recur (%treap-right treap))
                      (setf (%treap-right treap) left)
                      (values treap right)))
                   (t
                    (multiple-value-bind (left right)
                        (recur (%treap-left treap))
                      (setf (%treap-left treap) right)
                      (values left treap))))))
    (recur treap)))

(declaim (inline treap-insert))
(defun treap-insert (key treap &key (test #'<))
  "Destructively inserts KEY into TREAP and returns the resultant treap. You
cannot rely on the side effect. Use the returned value.

The behavior is undefined when duplicated keys are inserted."
  (declare ((or null treap) treap)
           (function test))
  (labels ((recur (node treap)
             (declare (treap node))
             (cond ((null treap) node)
                   ((> (%treap-priority node) (%treap-priority treap))
                    (setf (values (%treap-left node) (%treap-right node))
                          (treap-split (%treap-key node) treap :test test))
                    node)
                   (t
                    (if (funcall test (%treap-key node) (%treap-key treap))
                        (setf (%treap-left treap)
                              (recur node (%treap-left treap)))
                        (setf (%treap-right treap)
                              (recur node (%treap-right treap))))
                    treap))))
    (recur (make-treap key (random most-positive-fixnum)) treap)))

(defun treap-merge (left right)
  "Destructively merges two treaps. Assumes that all keys of LEFT are smaller (or larger,
depending on the order) than those of RIGHT."
  (declare #.OPT
           ((or null treap) left right))
  (cond ((null left) right)
        ((null right) left)
        ((> (%treap-priority left) (%treap-priority right))
         (setf (%treap-right left)
               (treap-merge (%treap-right left) right))
         left)
        (t
         (setf (%treap-left right)
               (treap-merge left (%treap-left right)))
         right)))

(declaim (inline treap-delete))
(defun treap-delete (key treap &key (test #'<))
  "Destructively deletes the KEY in TREAP and returns the result treap. You
cannot rely on the side effect. Use the returned value."
  (declare ((or null treap) treap)
           (function test))
  (labels ((recur (treap)
             (cond ((null treap) nil)
                   ((funcall test key (%treap-key treap))
                    (setf (%treap-left treap) (recur (%treap-left treap)))
                    treap)
                   ((funcall test (%treap-key treap) key)
                    (setf (%treap-right treap) (recur (%treap-right treap)))
                    treap)
                   (t
                    (treap-merge (%treap-left treap) (%treap-right treap))))))
    (recur treap)))

(declaim (ftype (function * (values (integer 0 #.most-positive-fixnum) &optional)) treap-count))
(defun treap-count (treap)
  (declare ((or null treap) treap))
  (if (null treap)
      0
      (+ 1 (treap-count (%treap-left treap)) (treap-count (%treap-right treap)))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare #.OPT)
  (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
                                  ;; (return-from read-fixnum 0)
                                  (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))))))))

(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 ()
  (declare #.OPT)
  (let* ((n (read))
         treap)
    (declare (uint32 n))
    (dotimes (_ n)
      (let ((a (read-fixnum)))
        (if (treap-find a treap)
            (setf treap (treap-delete a treap))
            (setf treap (treap-insert a treap)))))
    (println (treap-count treap))))

#-swank(main)


Measured memory_bytes: 25188