;; -*- 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
(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
                                  (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))))))))

;; Treap with implicit key for updating and querying interval.

(defconstant +op-identity+ most-positive-fixnum)

(defstruct (itreap (:constructor %make-itreap (value priority &key left right (count 1)))
                  (:copier nil)
                  (:conc-name %itreap-))
  (value +op-identity+ :type fixnum)
  (reversed nil :type boolean)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (count 1 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null itreap))
  (right nil :type (or null itreap)))

(declaim (inline itreap-count))
(defun itreap-count (itreap)
  (declare ((or null itreap) itreap))
  (if itreap
      (%itreap-count itreap)
      0))

(declaim (inline update-count))
(defun update-count (itreap)
  (declare (itreap itreap))
  (setf (%itreap-count itreap)
        (+ 1
           (itreap-count (%itreap-left itreap))
           (itreap-count (%itreap-right itreap)))))

(declaim (inline force-self))
(defun force-self (itreap)
  (declare (itreap itreap))
  (update-count itreap))

(declaim (inline force-down))
(defun force-down (itreap)
  (declare (itreap itreap))
  (when (%itreap-reversed itreap)
    (setf (%itreap-reversed itreap) nil)
    (rotatef (%itreap-left itreap) (%itreap-right itreap))
    (let ((left (%itreap-left itreap)))
      (when left
        (setf (%itreap-reversed left) (not (%itreap-reversed left)))))
    (let ((right (%itreap-right itreap)))
      (when right
        (setf (%itreap-reversed right) (not (%itreap-reversed right)))))))

(defun itreap-split (itreap index)
  "Destructively splits the ITREAP into two nodes [0, INDEX) and [INDEX, N), where N
  is the number of elements of the ITREAP."
  (declare #.OPT ((integer 0 #.most-positive-fixnum) index))
  (unless (<= index (itreap-count itreap))
    (error 'invalid-itreap-index-error :index index :itreap itreap))
  (labels ((recur (itreap pos)
             (unless itreap
               (return-from itreap-split (values nil nil)))
             (force-down itreap)
             (let ((implicit-key (1+ (itreap-count (%itreap-left itreap)))))
               (if (< pos implicit-key)
                   (multiple-value-bind (left right)
                       (itreap-split (%itreap-left itreap) pos)
                     (setf (%itreap-left itreap) right)
                     (force-self itreap)
                     (values left itreap))
                   (multiple-value-bind (left right)
                       (itreap-split (%itreap-right itreap) (- pos implicit-key))
                     (setf (%itreap-right itreap) left)
                     (force-self itreap)
                     (values itreap right))))))
    (recur itreap index)))

(defun itreap-merge (left right)
  "Destructively merges two ITREAPs."
  (declare #.OPT ((or null itreap) left right))
  (cond ((null left) (when right (force-down right) (force-self right)) right)
        ((null right) (when left (force-down left) (force-self left)) left)
        (t (force-down left)
           (force-down right)
           (if (> (%itreap-priority left) (%itreap-priority right))
               (progn
                 (setf (%itreap-right left)
                       (itreap-merge (%itreap-right left) right))
                 (force-self left)
                 left)
               (progn
                 (setf (%itreap-left right)
                       (itreap-merge left (%itreap-left right)))
                 (force-self right)
                 right)))))

(define-condition invalid-itreap-index-error (type-error)
  ((itreap :initarg :itreap :reader invalid-itreap-index-error-itreap)
   (index :initarg :index :reader invalid-itreap-index-error-index))
  (:report
   (lambda (condition stream)
     (format stream "Invalid index ~W for itreap ~W."
             (invalid-itreap-index-error-index condition)
             (invalid-itreap-index-error-itreap condition)))))

(defun itreap-insert (itreap index obj)
  "Destructively inserts OBJ into ITREAP and returns the resultant treap. You
cannot rely on the side effect. Use the returned value."
  (declare #.OPT ((or null itreap) itreap)
           ((integer 0 #.most-positive-fixnum) index))
  (unless (<= index (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index index))
  (let ((node (%make-itreap obj (random most-positive-fixnum))))
    (labels ((recur (itreap pos)
               (declare ((integer 0 #.most-positive-fixnum) pos))
               (unless itreap (return-from recur node))
               (force-down itreap)
               (if (> (%itreap-priority node) (%itreap-priority itreap))
                   (progn
                     (setf (values (%itreap-left node) (%itreap-right node))
                           (itreap-split itreap pos))
                     (force-self node)
                     node)
                   (let ((implicit-key (+ 1 (itreap-count (%itreap-left itreap)))))
                     (if (< pos implicit-key)
                         (setf (%itreap-left itreap)
                               (recur (%itreap-left itreap) pos))
                         (setf (%itreap-right itreap)
                               (recur (%itreap-right itreap) (- pos implicit-key))))
                     (force-self itreap)
                     itreap))))
      (recur itreap index))))

(declaim (inline itreap-map))
(defun itreap-map (function itreap)
  "Successively applies FUNCTION to ITREAP[0], ..., ITREAP[SIZE-1]."
  (labels ((recur (itreap)
             (when itreap
               (force-down itreap)
               (recur (%itreap-left itreap))
               (funcall function (%itreap-value itreap))
               (recur (%itreap-right itreap))
               (force-self itreap))))
    (recur itreap)))

(defmethod print-object ((object itreap) stream)
  (print-unreadable-object (object stream :type t)
    (let ((size (itreap-count object))
          (index 0))
      (declare ((integer 0 #.most-positive-fixnum) index))
      (itreap-map (lambda (x)
                   (princ x stream)
                   (incf index)
                   (when (< index size)
                     (write-char #\  stream)))
                 object))))

(defmacro do-itreap ((var itreap &optional result) &body body)
  "Successively binds ITREAP[0], ..., ITREAP[SIZE-1] to VAR and executes BODY."
  `(block nil
     (itreap-map (lambda (,var) ,@body) ,itreap)
     ,result))

(declaim (inline itreap-reverse))
(defun itreap-reverse (itreap l r)
  (declare ((integer 0 #.most-positive-fixnum) l r))
  (unless (<= l r (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index (cons l r)))
  (multiple-value-bind (itreap-0-l itreap-l-n)
      (itreap-split itreap l)
    (multiple-value-bind (itreap-l-r itreap-r-n)
        (itreap-split itreap-l-n (- r l))
      (setf (%itreap-reversed itreap-l-r) (not (%itreap-reversed itreap-l-r)))
      (itreap-merge itreap-0-l (itreap-merge itreap-l-r itreap-r-n)))))

(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)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Hauptteil

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (as (make-array n :element-type 'uint31))
         itreap)
    (declare (uint31 n))
    (dotimes (i n) (setf (aref as i) (read-fixnum)))
    (dotimes (i n)
      (setf itreap (itreap-insert itreap i (aref as i)))
      (setf itreap (itreap-reverse itreap 0 (1+ i))))
    (let ((i 0))
      (declare (uint31 i))
      (do-itreap (x itreap (terpri))
        (write x)
        (incf i)
        (when (< i n)
          (write-char #\ ))))))

#-swank(main)


Measured memory_bytes: 57060