(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

(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"
  (declare #.cl-user::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 #\-))
                                  (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))))))))

;;;
;;; Disjoint set (union by size & path compression)
;;;

(defpackage :cp/disjoint-set
  (:use :cl)
  (:export #:disjoint-set #:make-disjoint-set #:ds-data
           #:ds-root #:ds-unite! #:ds-connected-p #:ds-size))
(in-package :cp/disjoint-set)

(defstruct (disjoint-set
            (:constructor make-disjoint-set
                (size &aux (data (make-array size :element-type 'fixnum :initial-element -1))))
            (:conc-name ds-)
            (:predicate nil)
            (:copier nil))
  (data nil :type (simple-array fixnum (*))))

(declaim (inline ds-root))
(defun ds-root (disjoint-set x)
  "Returns the root of X."
  (declare ((mod #.array-total-size-limit) x))
  (let ((data (ds-data disjoint-set)))
    (labels ((recur (x)
               (if (< (aref data x) 0)
                   x
                   (setf (aref data x)
                         (recur (aref data x))))))
      (recur x))))

(declaim (inline ds-unite!))
(defun ds-unite! (disjoint-set x1 x2)
  "Destructively unites X1 and X2 and returns true iff X1 and X2 become
connected for the first time."
  (let ((root1 (ds-root disjoint-set x1))
        (root2 (ds-root disjoint-set x2)))
    (unless (= root1 root2)
      (let ((data (ds-data disjoint-set)))
        ;; NOTE: If you want X1 to always be root, just delete this form. (Time
        ;; complexity becomes worse, however.)
        (when (> (aref data root1) (aref data root2))
          (rotatef root1 root2))
        (incf (aref data root1) (aref data root2))
        (setf (aref data root2) root1)))))

(declaim (inline ds-connected-p))
(defun ds-connected-p (disjoint-set x1 x2)
  "Returns true iff X1 and X2 have the same root."
  (= (ds-root disjoint-set x1) (ds-root disjoint-set x2)))

(declaim (inline ds-size))
(defun ds-size (disjoint-set x)
  "Returns the size of the connected component to which X belongs."
  (- (aref (ds-data disjoint-set)
           (ds-root disjoint-set x))))

;;;
;;; Bucket sort and counting sort
;;;

(defpackage :cp/binsort
  (:use :cl)
  (:export #:map-binsorted #:do-binsorted #:binsort!))
(in-package :cp/binsort)

(declaim (inline map-binsorted))
(defun map-binsorted (function sequence range-max &key from-end key)
  "Calls FUNCTION with each ascending non-negative integer in SEQUENCE if KEY is
null. If KEY is non-nil, this function calls FUNCTION with each element of
SEQUENCE in the order of the (non-negative) integers that (FUNCALL KEY
<element>) returns. Any these integers must not exceed RANGE-MAX. If FROM-END is
true, the descending order is adopted instead. This function is
non-destructive."
  (declare ((mod #.array-total-size-limit) range-max))
  (if key
      (let ((buckets (make-array (1+ range-max) :element-type 'list :initial-element nil))
            (existing-min most-positive-fixnum)
            (existing-max 0))
        (declare (dynamic-extent buckets))
        (sequence:dosequence (e sequence)
          (let ((value (funcall key e)))
            (push e (aref buckets value))
            (setf existing-min (min value existing-min))
            (setf existing-max (max value existing-max))))
        (if from-end
            (loop for x from existing-max downto existing-min
                  do (dolist (e (aref buckets x))
                       (funcall function e)))
            (loop for x from existing-min to existing-max
                  do (dolist (e (aref buckets x))
                       (funcall function e)))))
      ;; If KEY is not given, all we need is counting sort.
      (let ((counts (make-array (1+ range-max) :element-type 'fixnum :initial-element 0))
            (existing-min most-positive-fixnum)
            (existing-max 0))
        (declare (dynamic-extent counts))
        (sequence:dosequence (e sequence)
          (incf (aref counts e))
          (setf existing-min (min e existing-min))
          (setf existing-max (max e existing-max)))
        (if from-end
            (loop for x from existing-max downto existing-min
                  do (loop repeat (aref counts x)
                           do (funcall function x)))
            (loop for x from existing-min to existing-max
                  do (loop repeat (aref counts x)
                           do (funcall function x)))))))

(defmacro do-binsorted ((var sequence range-max &key from-end key finally) &body body)
  "DO-style macro of MAP-BINSORTED"
  `(block nil
     (map-binsorted (lambda (,var) ,@body) ,sequence ,range-max
                    :from-end ,from-end :key ,key)
     ,finally))

;; not tested
(declaim (inline binsort!))
(defun binsort! (sequence range-max &key from-end key)
  (declare ((mod #.array-total-size-limit) range-max))
  (if key
      (let ((buckets (make-array (1+ range-max) :element-type 'list :initial-element nil)))
        (sequence:dosequence (e sequence)
          (push e (aref buckets (funcall key e))))
        (let ((pos 0))
          (declare ((integer 0 #.most-positive-fixnum) pos))
          (if from-end
              (loop for x from range-max downto 0
                    do (dolist (e (aref buckets x))
                         (setf (aref sequence pos) e)
                         (incf pos)))
              (loop for x from 0 to range-max
                    do (dolist (e (aref buckets x))
                         (setf (aref sequence pos) e)
                         (incf pos))))))
      ;; If KEY is not given, all we need is counting sort.
      (let ((counts (make-array (1+ range-max)
                                :element-type '(integer 0 #.most-positive-fixnum)
                                :initial-element 0)))
        (sequence:dosequence (e sequence)
          (incf (aref counts e)))
        (let ((pos 0))
          (declare ((integer 0 #.most-positive-fixnum) pos))
          (if from-end
              (loop for x from range-max downto 0
                    do (loop repeat (aref counts x)
                             do (setf (aref sequence pos) x)
                                (incf pos)))
              (loop for x from 0 to range-max
                    do (loop repeat (aref counts x)
                             do (setf (aref sequence pos) x)
                                (incf pos)))))))
  sequence)

;; BEGIN_USE_PACKAGE
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/binsort :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/disjoint-set :cl-user))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (use-package :cp/read-fixnum :cl-user))
(in-package :cl-user)

;;;
;;; Body
;;;

(defun main ()
  (declare (inline sort sb-impl::stable-sort-list))
  (let* ((n (read))
         (xs (make-array n :element-type 'uint31 :initial-element 0))
         (ys (make-array n :element-type 'uint31 :initial-element 0))
         (is-x (let ((tmp (make-array n :element-type 'uint31)))
                 (dotimes (i n tmp)
                   (setf (aref tmp i) i))))
         (is-y (let ((tmp (make-array n :element-type 'uint31)))
                 (dotimes (i n tmp)
                   (setf (aref tmp i) i))))
         (dset (make-disjoint-set n))
         stack)
    (dotimes (i n)
      (let ((x (- (read-fixnum) 1))
            (y (- (read-fixnum) 1)))
        (setf (aref xs i) x
              (aref ys i) y)))
    (binsort! is-x n :key (lambda (i) (aref xs i)))
    (binsort! is-y n :key (lambda (i) (aref ys i)))
    (dotimes (x1 n)
      (let* ((i1 (aref is-x x1))
             (y1 (aref ys i1)))
        (if stack
            (let ((top (car stack)))
              (if (< y1 top)
                  (push y1 stack)
                  (loop while stack
                        for y2 = (car stack)
                        for i2 = (aref is-y y2)
                        while (> y1 y2)
                        do (ds-unite! dset i1 i2)
                           (pop stack)
                        finally (push top stack))))
            (push y1 stack))))
    (write-string
     (with-output-to-string (*standard-output* nil :element-type 'base-char)
       (dotimes (i n)
         (println (ds-size dset i)))))))

#-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
  (5am:is
   (equal "1
1
2
2
"
          (run "4
1 4
2 3
3 1
4 2
" nil)))
  (5am:is
   (equal "3
3
1
1
2
3
2
"
          (run "7
6 4
4 3
3 5
7 1
2 7
5 2
1 6
" nil))))


Measured memory_bytes: 45720