(in-package :cl-user)
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx opt
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (set-dispatch-macro-character #\# #\> #'cl-debug-print:debug-print-reader)

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

(defconstant +mod+ 1000000007)

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

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

;; BEGIN_INSERTED_CONTENTS
;;;
;;; double-ended queue with ring-buffer
;;;

(defpackage :cp/deque
  (:use :cl)
  (:export #:deque-empty-error #:deque-invalid-index-error #:define-deque))
(in-package :cp/deque)

(declaim (inline %power-of-two-ceiling))
(defun %power-of-two-ceiling (x)
  (ash 1 (integer-length (- x 1))))

(deftype index () '(integer 0 #.(floor array-total-size-limit 2)))

(define-condition deque-empty-error (error)
  ((queue :initarg :queue :reader deque-empty-error-queue))
  (:report
   (lambda (condition stream)
     (format stream "Attempted to pop empty deque ~W" (deque-empty-error-queue condition)))))

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

;; TODO: detailed documentation
(defmacro define-deque (name &key (element-type 'fixnum))
  "Defines deque for given ELEMENT-TYPE.

constructor: MAKE-<NAME>.
basic operations: <NAME>-PUSH-FRONT, <NAME>-PUSH-BACK, <NAME>-POP-FRONT,
<NAME>-POP-BACK.
accessor: <NAME>-REF.
utilities: <NAME>-EMPTY-P, <NAME>-REINITIALIZE.
"
  (let ((push-front (intern (format nil "~A-PUSH-FRONT" name)))
        (push-back (intern (format nil "~A-PUSH-BACK" name)))
        (pop-front (intern (format nil "~A-POP-FRONT" name)))
        (pop-back (intern (format nil "~A-POP-BACK" name)))
        (peek-front (intern (format nil "~A-PEEK-FRONT" name)))
        (peek-back (intern (format nil "~A-PEEK-BACK" name)))
        (empty-p (intern (format nil "~A-EMPTY-P" name)))
        (constructor (intern (format nil "MAKE-~A" name)))
        (reinitializer (intern (format nil "~A-REINITIALIZE" name)))
        (reffer (intern (format nil "~A-REF" name)))
        (data-getter (intern (format nil "~A-DATA" name)))
        (front-getter (intern (format nil "~A-FRONT" name)))
        (count-getter (intern (format nil "~A-COUNT" name)))
        (adjuster (intern (format nil "%~A-ADJUST" name))))
    `(progn
       (defstruct (,name (:constructor ,constructor
                             (initial-size
                              &aux
                              (data (make-array (max 2 (%power-of-two-ceiling initial-size))
                                                :element-type ',element-type))))
                         (:copier nil)
                         (:predicate nil))
         (data nil :type (simple-array ,element-type (*)))
         (front 0 :type index)
         (count 0 :type index))
       (declaim (ftype (function (index) (values ,name &optional))
                       ,constructor))

       (defun ,adjuster (,name)
         ;; FIXME: change safety to zero when you believe this library is stable
         (declare (optimize (speed 3)))
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name))
                           (data (,data-getter ,name)))
           (let ((length (length data)))
             (when (= count length)
               (let ((new-data (make-array (* 2 length) :element-type ',element-type)))
                 (replace new-data data :start2 front)
                 (when (< length (+ front count))
                   (replace new-data data :start1 (- length front) :end2 front))
                 (setq data new-data
                       front 0))))))

       (declaim (inline ,push-front))
       (defun ,push-front (obj ,name)
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (,adjuster ,name)
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (next-front (logand mask (+ front mask))))
             (declare (index next-front))
             (setf (aref data next-front) obj)
             (setq front next-front)
             (incf count)
             ,name)))

       (declaim (inline ,pop-front))
       (defun ,pop-front (,name)
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (when (zerop count)
             (error 'deque-empty-error :queue ,name))
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (next (logand mask (+ front 1))))
             (declare (index next))
             (prog1 (aref data front)
               (setq front next)
               (decf count)))))

       (declaim (inline ,peek-front))
       (defun ,peek-front (,name)
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (when (zerop count)
             (error 'deque-empty-error :queue ,name))
           (let* ((data (,data-getter ,name)))
             (aref data front))))

       (declaim (inline ,push-back))
       (defun ,push-back (obj ,name)
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (,adjuster ,name)
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (pos (logand mask (+ front count))))
             (declare (index pos))
             (setf (aref data pos) obj)
             (incf count)
             ,name)))

       (declaim (inline ,pop-back))
       (defun ,pop-back (,name)
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (when (zerop count)
             (error 'deque-empty-error :queue ,name))
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (pos (logand mask (+ front count mask))))
             (declare (index pos))
             (decf count)
             (aref data pos))))

       (declaim (inline ,peek-back))
       (defun ,peek-back (,name)
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (when (zerop count)
             (error 'deque-empty-error :queue ,name))
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (pos (logand mask (+ front count mask))))
             (declare (index pos))
             (aref data pos))))

       (declaim (inline ,empty-p))
       (defun ,empty-p (,name)
         (zerop (,count-getter ,name)))

       (declaim (inline ,reinitializer))
       (defun ,reinitializer (,name)
         (setf (,count-getter ,name) 0))

       (declaim (inline ,reffer))
       (defun ,reffer (,name index)
         "Returns the INDEX-th element from the top. (0-based)"
         (declare (index index))
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (when (>= index count)
             (error 'deque-invalid-index-error :index index :queue ,name))
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (pos (logand mask (+ front index))))
             (declare (index pos))
             (aref data pos))))

       (declaim (inline (setf ,reffer)))
       (defun (setf ,reffer) (new-value ,name index)
         (declare (index index))
         (symbol-macrolet ((front (,front-getter ,name))
                           (count (,count-getter ,name)))
           (when (>= index count)
             (error 'deque-invalid-index-error :index index :queue ,name))
           (let* ((data (,data-getter ,name))
                  (length (length data))
                  (mask (- length 1))
                  (pos (logand mask (+ front index))))
             (declare (index pos))
             (setf (aref data pos) new-value)))))))

#+(or)
(define-deque deque :element-type fixnum)

(defpackage :cp/read-fixnum
  (:use :cl)
  (:export #:read-fixnum))
(in-package :cp/read-fixnum)

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (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 #\-))
                                  (setq 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 explicit key
;;; Virtually it works like std::map, std::multiset, or java.util.TreeMap.
;;;

(defpackage :cp/explicit-treap
  (:use :cl)
  (:export #:treap #:treap-p #:treap-key #:treap-accumulator
           #:treap-split #:treap-insert #:treap-merge #:treap-delete
           #:treap-ensure-key #:treap-unite #:treap-map #:do-treap
           #:make-treap #:treap-fold #:treap-update #:treap-ref
           #:treap-first #:treap-last #:treap-find
           #:treap-bisect-left #:treap-bisect-right #:treap-bisect-left-1 #:treap-bisect-right-1
           #:treap-fold-bisect #:treap-fold-bisect-from-end))
(in-package :cp/explicit-treap)

;; Tips to use this structure as a multiset: Just define OP as (defun op (x y)
;; (+ x y)) and insert each element by
;;
;; (treap-ensure-key <treap> <key> 1 :if-exists #'1+)
;;
;; instead of TREAP-INSERT.

;; TODO & NOTE: insufficient tests
;; TODO: introduce abstraction by macro

(defconstant +op-identity+ nil
  "identity element w.r.t. OP")

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

(declaim (inline treap-key))
(defun treap-key (treap)
  "Returns the key of (nullable) TREAP."
  (and treap (%treap-key treap)))

(declaim (ftype (function * (values (or null treap) (or null treap) &optional)) treap-split))
(defun treap-split (treap key &key (order #'<))
  "Destructively splits TREAP with reference to KEY and returns two treaps,
the smaller sub-treap (< KEY) and the larger one (>= KEY)."
  (declare (function order)
           ((or null treap) treap))
  (if (null treap)
      (values nil nil)
      (progn
        (if (funcall order (%treap-key treap) key)
            (multiple-value-bind (left right)
                (treap-split (%treap-right treap) key :order order)
              (setf (%treap-right treap) left)
              (values treap right))
            (multiple-value-bind (left right)
                (treap-split (%treap-left treap) key :order order)
              (setf (%treap-left treap) right)
              (values left treap))))))

(declaim (inline treap-insert))
(defun treap-insert (treap key value &key (order #'<))
  "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 duplicate keys are inserted."
  (declare ((or null treap) treap)
           (function order))
  (labels ((recur (node treap)
             (declare (treap node))
             (unless treap (return-from recur node))
             (if (> (%treap-priority node) (%treap-priority treap))
                 (progn
                   (setf (values (%treap-left node) (%treap-right node))
                         (treap-split treap (%treap-key node) :order order))
                   node)
                 (progn
                   (if (funcall order (%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) value) treap)))

(declaim (inline treap-ensure-key))
(defun treap-ensure-key (treap key value &key (order #'<) if-exists)
  "IF-EXISTS := nil | function

Ensures that TREAP contains KEY and assigns VALUE to it if IF-EXISTS is
false. If IF-EXISTS is function and TREAP already contains KEY, TREAP-ENSURE-KEY
updates the value by the function instead of overwriting it with VALUE."
  (declare (function order)
           ((or null treap) treap))
  (labels ((find-and-update (treap)
             ;; Updates the value slot and returns T if KEY exists
             (unless treap (return-from find-and-update nil))
             (cond ((funcall order key (%treap-key treap))
                    (when (find-and-update (%treap-left treap))
                      t))
                   ((funcall order (%treap-key treap) key)
                    (when (find-and-update (%treap-right treap))
                      t))
                   (t (setf (%treap-value treap)
                            (if if-exists
                                (funcall if-exists (%treap-value treap))
                                value))
                      t))))
    (if (find-and-update treap)
        treap
        (treap-insert treap key value :order order))))

(defun treap-merge (left right)
  "Destructively concatenates two treaps. Assumes that all keys of LEFT are
smaller (or larger, depending on the order) than those of RIGHT.

Note that this `merge' is different from CL:MERGE and rather close to
CL:CONCATENATE."
  (declare (optimize (speed 3))
           ((or null treap) left right))
  (cond ((null left)  right)
        ((null right)  left)
        (t (if (> (%treap-priority left) (%treap-priority right))
               (progn
                 (setf (%treap-right left)
                       (treap-merge (%treap-right left) right))
                 left)
               (progn
                 (setf (%treap-left right)
                       (treap-merge left (%treap-left right)))
                 right)))))

(defun treap-delete (treap key &key (order #'<))
  "Destructively deletes KEY in TREAP and returns the resultant treap. Returns
unmodified TREAP If KEY doesn't exist. You cannot rely on the side effect. Use
the returned value.

 (Note that this function deletes at most one node even if duplicate keys
exist.)"
  (declare ((or null treap) treap)
           (function order))
  (when treap
    (cond ((funcall order key (%treap-key treap))
           (setf (%treap-left treap)
                 (treap-delete (%treap-left treap) key :order order))
           treap)
          ((funcall order (%treap-key treap) key)
           (setf (%treap-right treap)
                 (treap-delete (%treap-right treap) key :order order))
           treap)
          (t
           (treap-merge (%treap-left treap) (%treap-right treap))))))

(declaim (inline treap-map))
(defun treap-map (function treap)
  "Successively applies FUNCTION to TREAP[0], ..., TREAP[SIZE-1]. FUNCTION must
take two arguments: KEY and VALUE."
  (labels ((recur (treap)
             (when treap
               (recur (%treap-left treap))
               (funcall function (%treap-key treap) (%treap-value treap))
               (recur (%treap-right treap)))))
    (recur treap)))

(defmethod print-object ((object treap) stream)
  (print-unreadable-object (object stream :type t)
    (let ((init t))
      (treap-map (lambda (key value)
                   (if init
                       (setf init nil)
                       (write-char #\  stream))
                   (format stream "<~A . ~A>" key value))
                 object))))

(defmacro do-treap ((key-var value-var treap &optional result) &body body)
  "Successively binds the keys and the values of INODE[0], ..., INODE[SIZE-1] to
KEY-VAR and VALUE-VAR and executes BODY."
  `(block nil
     (treap-map (lambda (,key-var ,value-var) ,@body) ,treap)
     ,result))

;; This function takes O(nlog(n)) time. It is just for debugging.
(defun treap (order &rest key-and-values)
  "Takes cons cells in the form of (<key> . <value>)."
  (loop with res = nil
        for (key . value) in key-and-values
        do (setf res (treap-insert res key value :order order))
        finally (return res)))

;; Reference: https://cp-algorithms.com/data_structures/treap.html
;; TODO: take a sorted list as the argument
(declaim (inline make-treap))
(defun make-treap (sorted-vector)
  "Makes a treap using each key of SORTED-VECTOR in O(n) time. Note that this
function doesn't check if the SORTED-VECTOR is actually sorted w.r.t. your
intended order. The values are filled with the identity element."
  (declare (vector sorted-vector))
  (labels ((heapify (top)
             (when top
               (let ((prioritized-node top))
                 (when (and (%treap-left top)
                            (> (%treap-priority (%treap-left top))
                               (%treap-priority prioritized-node)))
                   (setq prioritized-node (%treap-left top)))
                 (when (and (%treap-right top)
                            (> (%treap-priority (%treap-right top))
                               (%treap-priority prioritized-node)))
                   (setq prioritized-node (%treap-right top)))
                 (unless (eql prioritized-node top)
                   (rotatef (%treap-priority prioritized-node)
                            (%treap-priority top))
                   (heapify prioritized-node)))))
           (build (l r)
             (declare ((integer 0 #.most-positive-fixnum) l r))
             (if (= l r)
                 nil
                 (let* ((mid (ash (+ l r) -1))
                        (node (%make-treap (aref sorted-vector mid)
                                           (random most-positive-fixnum)
                                           +op-identity+)))
                   (setf (%treap-left node) (build l mid))
                   (setf (%treap-right node) (build (+ mid 1) r))
                   (heapify node)
                   node))))
    (build 0 (length sorted-vector))))

(declaim (inline treap-ref))
(defun treap-ref (treap key &key (order #'<))
  (declare ((or null treap) treap))
  (labels ((recur (treap)
             (when treap
               (prog1 (cond ((funcall order key (%treap-key treap))
                             (recur (%treap-left treap)))
                            ((funcall order (%treap-key treap) key)
                             (recur (%treap-right treap)))
                            (t (%treap-value treap)))))))
    (recur treap)))

(declaim (inline (setf treap-ref)))
(defun (setf treap-ref) (new-value treap key &key (order #'<))
  (declare ((or null treap) treap))
  (labels ((recur (treap)
             (when treap
               (prog1 (cond ((funcall order key (%treap-key treap))
                             (recur (%treap-left treap)))
                            ((funcall order (%treap-key treap) key)
                             (recur (%treap-right treap)))
                            (t (setf (%treap-value treap) new-value)))))))
    (recur treap)))

(defun treap-first (treap)
  (declare (optimize (speed 3))
           (treap treap))
  (if (%treap-left treap)
      (treap-first (%treap-left treap))
      (%treap-key treap)))

(defun treap-last (treap)
  (declare (optimize (speed 3))
           (treap treap))
  (if (%treap-right treap)
      (treap-last (%treap-right treap))
      (%treap-key treap)))

;;;
;;; Binary search w.r.t. key
;;;

;; NOTE: These functions intentionally don't return the assigned value. That is
;; for efficiency, because thereby they don't need to execute lazy propagation.

(defun treap-find (treap key &key (order #'<))
  "Finds the key that satisfies (AND (NOT (FUNCALL ORDER KEY (%TREAP-KEY
<sub-treap>))) (NOT (FUNCALL ORDER (%TREAP-KEY <sub-treap>) KEY))) and returns
KEY if it exists, otherwise returns NIL."
  (declare (optimize (speed 3))
           (function order)
           ((or null treap) treap))
  (cond ((null treap) nil)
        ((funcall order key (%treap-key treap))
         (treap-find (%treap-left treap) key :order order))
        ((funcall order (%treap-key treap) key)
         (treap-find (%treap-right treap) key :order order))
        (t key)))

(declaim (inline treap-bisect-left))
(defun treap-bisect-left (treap key &key (order #'<))
  "Returns the smallest key equal to or larger than KEY. Returns NIL if KEY is
larger than any keys in TREAP."
  (declare ((or null treap) treap)
           (function order))
  (labels ((recur (treap)
             (unless treap (return-from recur nil))
             (if (funcall order (%treap-key treap) key)
                 (recur (%treap-right treap))
                 (or (recur (%treap-left treap))
                     treap))))
    (treap-key (recur treap))))

(declaim (inline treap-bisect-left))
(defun treap-bisect-right (treap key &key (order #'<))
  "Returns the smallest key larger than KEY. Returns NIL if KEY is equal to or
larger than any keys in TREAP."
  (declare ((or null treap) treap)
           (function order))
  (labels ((recur (treap)
             (unless treap (return-from recur nil))
             (if (funcall order key (%treap-key treap))
                 (or (recur (%treap-left treap))
                     treap)
                 (recur (%treap-right treap)))))
    (treap-key (recur treap))))

(declaim (inline treap-bisect-left-1))
(defun treap-bisect-left-1 (treap key &key (order #'<))
  "Returns the largest key smaller than KEY. Returns NIL if KEY is equal to or
smaller than any keys in TREAP."
  (declare ((or null treap) treap)
           (function order))
  (labels ((recur (treap)
             (unless treap (return-from recur nil))
             (if (funcall order (%treap-key treap) key)
                 (or (recur (%treap-right treap))
                     treap)
                 (recur (%treap-left treap)))))
    (treap-key (recur treap))))

(declaim (inline treap-bisect-right-1))
(defun treap-bisect-right-1 (treap key &key (order #'<))
  "Returns the largest key equal to or smaller than KEY. Returns NIL if KEY is
smaller than any keys in TREAP."
  (declare ((or null treap) treap)
           (function order))
  (labels ((recur (treap)
             (unless treap (return-from recur nil))
             (if (funcall order key (%treap-key treap))
                 (recur (%treap-left treap))
                 (or (recur (%treap-right treap))
                     treap))))
    (treap-key (recur treap))))

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/explicit-treap :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/read-fixnum :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/deque :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(define-deque deque :element-type uint31)
(defun main ()
  (let* ((n (read))
         (acounter (make-array (+ n 1) :element-type 'uint31 :initial-element 0))
         (bdeq (make-deque n))
         treap)
    (dotimes (i n)
      (let ((a (read-fixnum)))
        (incf (aref acounter a))))
    (dotimes (i n)
      (let ((b (read-fixnum)))
        (deque-push-back b bdeq)))
    (dotimes (a (+ n 1))
      (let (current-list)
        (dotimes (_ (aref acounter a))
          (cond ((/= a (deque-peek-back bdeq))
                 (let ((b (deque-pop-back bdeq)))
                   (push (cons a b) current-list)))
                ((/= a (deque-peek-front bdeq))
                 (let ((b (deque-pop-front bdeq)))
                   (push (cons a b) current-list)))
                ;; 残りのbの中にaと一致するものしかない場合
                ((null treap)
                 (write-line "No")
                 (return-from main))
                (t (deque-pop-back bdeq)
                   (let ((prev-last-b (treap-last treap))
                         (prev-first-b (treap-first treap)))
                     (cond ((/= a prev-last-b)
                            ;; a-a cand-a(=alistの先頭)-prev-last-bを入れ替える
                            (let ((cand-a (pop (treap-ref treap prev-last-b))))
                              (assert (/= cand-a a))
                              (when (null (treap-ref treap prev-last-b))
                                (setq treap (treap-delete treap prev-last-b)))
                              (push (cons a prev-last-b) current-list)
                              (push (cons cand-a a) current-list)))
                           ((/= a prev-first-b)
                            ;; a-aとcand-a(=alistの先頭)-prev-first-bを入れ替える
                            (let ((cand-a (pop (treap-ref treap prev-first-b))))
                              (assert (/= cand-a a))
                              (when (null (treap-ref treap prev-first-b))
                                (setq treap (treap-delete treap prev-first-b)))
                              (push (cons a prev-first-b) current-list)
                              (push (cons cand-a a) current-list)))
                           (t (write-line "No")
                              (return-from main)))))))
        ;; 全部終わったらcurrent-listをtreapに記録
        (loop for (a . b) in current-list
              do (assert (/= a b))
                 (unless (treap-find treap b)
                   (setq treap (treap-insert treap b nil)))
                 (push a (treap-ref treap b)))))
    (let (res
          (init t))
      (treap-map (lambda (b alist)
                   (dolist (a alist)
                     (push (cons a b) res)))
                 treap)
      (write-line "Yes")
      (setq res (sort res #'< :key #'car))
      (write-string
       (with-output-to-string (*standard-output* nil :element-type 'base-char)
         (loop for (a . b) in res
               do (if init
                      (setq init nil)
                      (write-char #\ ))
                  (write b))))
      (terpri))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    #+os-windows (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)
    #+os-unix (run-program "xsel" '("-b" "-o") :output out :search t)))

#+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*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let* ((*standard-output* (or out (make-string-output-stream)))
         (res (etypecase thing
                (null
                 (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
                 (with-open-file (*standard-input* thing)
                   (main))))))
    (if out res (get-output-stream-string *standard-output*))))

#+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)))

#-swank
(eval-when (:compile-toplevel)
  (when (and (boundp 'sb-c::*compiler-warning-count*)
             (> sb-c::*compiler-warning-count* 0))
    (sb-ext:quit :unix-status 1)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (equal "Yes
2 2 3 1 1 1
"
          (run "6
1 1 1 2 2 3
1 1 1 2 2 3
" nil)))
  (it.bese.fiveam:is
   (equal "No
"
          (run "3
1 1 2
1 1 3
" nil)))
  (it.bese.fiveam:is
   (equal "Yes
3 3 1 2
"
          (run "4
1 1 2 3
1 2 3 3
" nil))))


Measured memory_bytes: 55972