;; -*- coding: utf-8 -*-
(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
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:defknown popcnt ((unsigned-byte 64)) (integer 0 64)
      (sb-c:foldable sb-c:flushable sb-c:movable)
    :overwrite-fndb-silently t)

  (sb-c:defknown popcnt ((unsigned-byte 64)) (integer 0 64)
      (sb-c:foldable sb-c:flushable sb-c:movable)
    :overwrite-fndb-silently t)

  (sb-vm::define-vop (popcnt)
    (:policy :fast-safe)
    (:translate popcnt)
    (:args (x :scs (sb-vm::unsigned-reg) :target r))
    (:arg-types sb-vm::unsigned-num)
    (:results (r :scs (sb-vm::unsigned-reg)))
    (:result-types sb-vm::unsigned-num)
    (:generator 3
                (unless (sb-vm::location= r x)
                  (sb-vm::inst xor r r))
                (sb-vm::inst popcnt r x)))

  (sb-vm::define-vop (popcnt/fx)
    (:policy :fast-safe)
    (:translate popcnt)
    (:args (x :scs (sb-vm::unsigned-reg) :target r))
    (:arg-types sb-vm::positive-fixnum)
    (:results (r :scs (sb-vm::unsigned-reg)))
    (:result-types sb-vm::unsigned-num)
    (:generator 2
                (unless (sb-vm::location= r x)
                  (sb-vm::inst xor r r))
                (sb-vm::inst popcnt r x))))

(defun popcnt (x)
  (popcnt x))

(declaim (inline shuffle!))
(defun shuffle! (vector)
  "Destructively shuffles VECTOR by Fisher-Yates algorithm."
  (declare (vector vector))
  (loop for i from (- (length vector) 1) above 0
        for j = (random (+ i 1))
        do (rotatef (aref vector i) (aref vector j)))
  vector)

;;;
;;; Succinct bit vector
;;;

;; REVIEW: Is it really better to use the typical three-layer succint bit vector
;; in competitive programming? It may be efficient to use a two-layer (not
;; succinct but compact) bit vector preserving the original vector and the
;; cumulative sum per 64-bit word.

(eval-when (:compile-toplevel :load-toplevel :execute)
  (assert (= sb-vm:n-word-bits 64)))

(defstruct (succinct-bit-vector (:constructor %make-sucbv (storage blocks))
                                (:conc-name sucbv-)
                                (:copier nil))
  (storage nil :type simple-bit-vector)
  (blocks nil :type (simple-array (unsigned-byte 31) (*))))

(defun make-sucbv! (vector)
  "The consequence is undefined when VECTOR is modified after a succinct bit
vector is created."
  (declare (optimize (speed 3)))
  (check-type vector simple-bit-vector)
  (let* ((vector (if (zerop (mod (length vector) sb-vm:n-word-bits))
                     vector
                     (adjust-array vector
                                   (* sb-vm:n-word-bits (ceiling (length vector) sb-vm:n-word-bits))
                                   :initial-element 0)))
         (len (length vector))
         (block-count (floor len sb-vm:n-word-bits))
         (blocks (make-array (+ 1 block-count)
                             :element-type '(unsigned-byte 31)
                             :initial-element 0))
         (sum 0))
    (declare (simple-bit-vector vector)
             ((integer 0 #.most-positive-fixnum) sum))
    (dotimes (i block-count)
      (setf (aref blocks i) sum)
      (incf sum (popcnt (sb-kernel:%vector-raw-bits vector i))))
    (setf (aref blocks block-count) sum)
    (%make-sucbv vector blocks)))

(declaim (inline sucbv-ref))
(defun sucbv-ref (sucbv index)
  (sbit (sucbv-storage sucbv) index))

;; NOTE: No error handling.
(declaim (inline sucbv-rank)
         (ftype (function * (values (integer 0 #.most-positive-fixnum) &optional)) sucbv-rank))
(defun sucbv-rank (sucbv end)
  "Counts the number of 1's in the range [0, END)."
  (declare #.OPT
           ((integer 0 #.most-positive-fixnum) end))
  (let* ((storage (sucbv-storage sucbv))
         (blocks (sucbv-blocks sucbv))
         (bpos (ash end -6))
         (brem (logand #b111111 end)))
    (+ (aref blocks bpos)
       (popcnt (ldb (byte brem 0)
                    (sb-kernel:%vector-raw-bits storage bpos))))))

;;;
;;; Wavelet matrix
;;;

(deftype wavelet-integer () '(integer 0 #.most-positive-fixnum))

(defstruct (wavelet-matrix (:constructor %make-wavelet-matrix
                               (length data zeros
                                &aux (depth (array-dimension data 0))))
                           (:copier nil)
                           (:conc-name wavelet-))
  (depth 0 :type (integer 1 #.most-positive-fixnum))
  (length 0 :type (integer 0 #.most-positive-fixnum))
  (data nil :type (simple-array succinct-bit-vector (*)))
  (zeros nil :type (simple-array (integer 0 #.most-positive-fixnum) (*))))

#+sbcl
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:defknown make-wavelet ((integer 1 #.most-positive-fixnum) vector)
      wavelet-matrix (sb-c:flushable)
    :overwrite-fndb-silently t))

;; TODO: add deftransform for better type derivation
(defun make-wavelet (bit-depth vector)
  (declare ((integer 1 #.most-positive-fixnum) bit-depth))
  (let* ((len (length vector))
         (fitted-len (* sb-vm:n-word-bits (ceiling len sb-vm:n-word-bits)))
         (data (locally (declare #+sbcl (muffle-conditions style-warning))
                 (make-array bit-depth :element-type 'succinct-bit-vector)))
         (zeros (make-array bit-depth :element-type '(integer 0 #.most-positive-fixnum)))
         (tmp (copy-seq vector))
         (lefts (make-array len :element-type (array-element-type vector)))
         (rights (make-array len :element-type (array-element-type vector)))
         (bits (make-array fitted-len :element-type 'bit)))
    (declare ((integer 0 #.most-positive-fixnum) len fitted-len)
             (vector tmp))
    (loop for d from (- bit-depth 1) downto 0
          do (let ((lpos 0)
                   (rpos 0))
               (declare ((integer 0 #.most-positive-fixnum) lpos rpos))
               (dotimes (i len)
                 (let ((bit (logand 1 (ash (aref tmp i) (- d)))))
                   (if (zerop bit)
                       (setf (aref lefts lpos) (aref tmp i)
                             lpos (+ lpos 1))
                       (setf (aref rights rpos) (aref tmp i)
                             rpos (+ rpos 1)))
                   (setf (aref bits i) bit)))
               (setf (aref data d) (make-sucbv! (copy-seq bits))
                     (aref zeros d) lpos)
               (rotatef lefts tmp)
               (replace tmp rights :start1 lpos :end2 rpos)))
    (%make-wavelet-matrix len data zeros)))

(define-condition invalid-wavelet-index-error (type-error)
  ((wavelet :initarg :wavelet :reader invalid-wavelet-index-error-wavelet)
   (index :initarg :index :reader invalid-wavelet-index-error-index))
  (:report
   (lambda (condition stream)
     (let ((index (invalid-wavelet-index-error-index condition)))
       (if (consp index)
           (format stream "Invalid range [~W, ~W) for wavelet-matrix ~W."
                   (car index)
                   (cdr index)
                   (invalid-wavelet-index-error-wavelet condition))
           (format stream "Invalid index ~W for wavelet-matrix ~W."
                   index
                   (invalid-wavelet-index-error-wavelet condition)))))))

(declaim (ftype (function * (values (unsigned-byte 31) &optional)) wavelet-range-count))
(defun wavelet-range-count (wmatrix lo hi &key (start 0) end)
  (declare #.OPT
           ((integer 0 #.most-positive-fixnum) lo hi start)
           ((or null (integer 0 #.most-positive-fixnum)) end))
  (let ((data (wavelet-data wmatrix))
        (zeros (wavelet-zeros wmatrix))
        (end (or end (wavelet-length wmatrix))))
    (labels
        ((dfs (depth start end value)
           (declare ((integer 0 #.most-positive-fixnum) start end value)
                    ((integer -1 #.most-positive-fixnum) depth)
                    (values (integer 0 #.most-positive-fixnum) &optional))
           (cond ((or (= start end)
                      (<= hi value))
                  0)
                 ((= depth -1)
                  (if (< value lo)
                      0
                      (- end start)))
                 (t
                  (let* ((next-value (logior value
                                             (the wavelet-integer (ash 1 depth))))
                         (upper-bound (logior next-value
                                              (- (the wavelet-integer (ash 1 depth)) 1))))
                    (cond ((< upper-bound lo)
                           0)
                          ((and (<= lo value) (< upper-bound hi))
                           (- end start))
                          (t
                           (let ((lcount (sucbv-rank (aref data depth) start))
                                 (rcount (sucbv-rank (aref data depth) end)))
                             (+ (dfs (- depth 1)
                                     (- start lcount)
                                     (- end rcount)
                                     value)
                                (dfs (- depth 1)
                                     (+ (aref zeros depth) lcount)
                                     (+ (aref zeros depth) rcount)
                                     next-value))))))))))
      (dfs (- (wavelet-depth wmatrix) 1) start end 0))))

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

(defconstant +inf+ (- (expt 2 11) 1))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (ws-plan (make-array (* 2 n) :element-type 'uint16 :initial-element +inf+))
         (bs-plan (make-array (* 2 n) :element-type 'uint16 :initial-element +inf+))
         (ws-pos (make-array (+ n 1) :element-type 'uint16))
         (bs-pos (make-array (+ n 1) :element-type 'uint16))
         (dp (make-array (list (+ n 1) (+ n 1))
                         :element-type 'uint32
                         :initial-element 0)))
    (declare (uint16 n))
    (dotimes (i (* 2 n))
      (let ((col (read))
            (a (read)))
        (if (eql col 'w)
            (setf (aref ws-plan i) a
                  (aref ws-pos a) i)
            (setf (aref bs-plan i) a
                  (aref bs-pos a) i))))
    (let ((ws-plan (make-wavelet 11 ws-plan))
          (bs-plan (make-wavelet 11 bs-plan))
          (values1 (make-array (+ 1 n) :element-type 'uint31))
          (values3 (make-array (+ 1 n) :element-type 'uint31)))
      (loop
        for x from 1 to n
        do (setf (aref values1 x)
                 (wavelet-range-count ws-plan 0 x :start (+ (aref ws-pos x) 1))))
      (loop
        for y from 1 to n
        do (setf (aref values3 y)
                 (wavelet-range-count bs-plan 0 y :start (+ (aref bs-pos y) 1))))
      (loop
        for x from 0 to n
        do (loop
             for y from 0 to n
             do (unless (= x y 0)
                  (setf (aref dp x y)
                        (min
                         (if (zerop y)
                             #xffffffff
                             (let ((pos (aref bs-pos y)))
                               (+ (aref dp x (- y 1))
                                  (wavelet-range-count ws-plan 0 (+ x 1) :start (+ pos 1))
                                  (aref values3 y))))
                         (if (zerop x)
                             #xffffffff
                             (let ((pos (aref ws-pos x)))
                               (+ (aref dp (- x 1) y)
                                  (aref values1 x)
                                  (wavelet-range-count bs-plan 0 (+ y 1) :start (+ pos 1)))))))))))
    (println (aref dp n n))))

#-swank (main)

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

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    ;; (run-program "C:/Windows/System32/WindowsPowerShell/v1.0/powershell.exe" '("get-clipboard") :output out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :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* out))
    (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))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "2000~%")
    (let ((vec (make-array 4000)))
      (dotimes (i 2000)
        (setf (aref vec i) (cons 'w (* i 1))
              (aref vec (+ i 2000)) (cons 'b (+ i 1))))
      (shuffle! vec)
      (loop for (col . num) across vec
            do (format out "~A ~A~%" col num)))))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3
B 1
W 2
B 3
W 1
W 3
B 2
"
    "4
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1
"
    "18
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7
"
    "41
")))


Measured memory_bytes: 62432