(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
(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (terminate-char #\Space))
  "Note that the returned string will be reused."
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let ((,buffer (load-time-value (make-string ,buffer-size
                                                  :element-type 'base-char))))
       (declare (simple-base-string ,buffer))
       (loop for ,character of-type base-char =
                #-swank (code-char (read-byte ,in nil #.(char-code #\Newline)))
                #+swank (read-char ,in nil #\Newline)
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (setf (schar ,buffer ,idx) ,terminate-char)
                     (return (values ,buffer ,idx))))))

(declaim (inline split-ints-into-vector))
(defun split-ints-into-vector (string dest-vector &key (offset 0) (key #'identity))
  (declare (string string)
           (function key)
           ((array * (*)) dest-vector)
           ((integer 0 #.most-positive-fixnum) offset))
  (loop with position = 0
        for idx from offset below (length dest-vector)
        do (setf (values (aref dest-vector idx) position)
                 (parse-integer string :start position :junk-allowed t))
           (setf (aref dest-vector idx) (funcall key (aref dest-vector idx)))
        finally (return dest-vector)))

(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
(declaim ((simple-array double-float (*)) *bernoulli*))
(defparameter *bernoulli*
  #.(coerce
     (mapcar (lambda (x) (float x 1d0))
             '(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30 0 5/66 0 -691/2730 0 7/6 0 -3617/510 0 43867/798 0 -174611/330 0 854513/138 0 -236364091/2730 0 8553103/6 0 -23749461029/870 0 8615841276005/14332 0))
     '(simple-array double-float (*))))

(declaim (ftype (function * (values double-float &optional)) log-factorial))
(defun log-factorial (n &optional (terms 2))
  (declare (optimize (speed 3))
           ((integer 0) n)
           ((unsigned-byte 8) terms))
  (if (or (= n 0) (= n 1))
      0d0
      (let ((n (float n 1d0)))
        (+ #.(log (sqrt (* 2 pi)))
           (* (+ n 0.5d0) (log n))
           (- n)
           (loop for i2 from 2 to (* terms 2) by 2
                 sum (/ (aref *bernoulli* i2)
                        (* i2 (- i2 1) (expt n (- i2 1))))
                 of-type double-float)))))

(defun log-binomial (n k &optional (terms 2))
  (declare ((integer 0) n k))
  (assert (>= n k))
  (- (log-factorial n terms)
     (log-factorial (- n k) terms)
     (log-factorial k terms)))

(declaim (inline bisect-nearest))
(defun bisect-nearest (value vector &key (start 0) end)
  (if (<= value (aref vector start))
      (aref vector start)
      (labels ((%bisect (lo hi)
                 (declare ((integer 0 #.most-positive-fixnum) hi lo))
                 (if (<= (- hi lo) 1)
                     (if (or (= (length vector) hi)
                             (>= (- (aref vector hi) value)
                                (- value (aref vector lo))))
                         (aref vector lo)
                         (aref vector hi))
                     (let ((mid (ash (+ hi lo) -1)))
                       (if (<= (aref vector mid) value)
                           (%bisect mid hi)
                           (%bisect lo mid))))))
        (%bisect start (or end (length vector))))))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (as (make-array n :element-type 'uint31)))
    (split-ints-into-vector (buffered-read-line 1100001) as)
    (setf as (sort as #'<))
    (loop for i from 1 below n
          with max = -1
          with a1 = -1
          with a2 = -1
          do (let* ((a/2 (bisect-nearest (* 0.5d0 (aref as i)) as :end i))
                    (b (log-binomial (aref as i) a/2)))
               (when (< max b)
                 (setf max b
                       a1 (aref as i)
                       a2 a/2)))
          finally (format t "~A ~A~%" a1 a2))))

#-swank(main)


Measured memory_bytes: 31208