(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
(setf *print-circle* t)

;; Treap with implicit key for updating point and querying interval or point.
;; This implementation includes the reverse operation of a interval though it
;; will rarely be used.

(defstruct (inode (:constructor %make-inode (value priority &key left right (count 1) (accumulator 0)))
                  (:copier nil)
                  (:conc-name %inode-))
  (value 0 :type fixnum)
  (accumulator 0 :type fixnum) ; e.g. MIN, MAX, SUM, ...
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (count 1 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null inode))
  (right nil :type (or null inode)))

(defmacro op (&rest args)
  `(max ,@args))

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

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

(declaim (inline update-accumulator))
(defun update-accumulator (inode)
  (declare (inode inode))
  (setf (%inode-accumulator inode)
        (if (%inode-left inode)
            (if (%inode-right inode)
                (op (%inode-accumulator (%inode-left inode))
                    (op (%inode-value inode)
                        (%inode-accumulator (%inode-right inode))))
                (op (%inode-accumulator (%inode-left inode))
                    (%inode-value inode)))
            (if (%inode-right inode)
                (op (%inode-value inode)
                    (%inode-accumulator (%inode-right inode)))
                (%inode-value inode)))))

(declaim (inline force-self))
(defun force-self (inode)
  (declare (inode inode))
  (update-count inode)
  (update-accumulator inode))

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

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

(declaim (inline log2-ceil))
(defun log2-ceil (n) (integer-length (- n 1)))

(defun make-inode (min-count initial-element)
  "(OP INITIAL-ELEMENT INITIAL-ELEMENT) must be equal to INITIAL-ELEMENT."
  (declare #.OPT ((integer 0 #.most-positive-fixnum) min-count))
  (when (zerop min-count)
    (return-from make-inode nil))
  (let* ((max-depth (log2-ceil (1+ min-count))) ; Needs depth = log(N+1) for N nodes.
         (count (- (ash 1 max-depth) 1)) ; 2^d-1 nodes for depth d
         (width (floor most-positive-fixnum count)) ; step size of priorities
         )
    (labels ((recurse (depth)
               (declare ((integer 0 #.(integer-length most-positive-fixnum)) depth))
               (if (= depth max-depth)
                   nil
                   ;; the beginning node at depth = d has the 2^(d+1)-1-th highest
                   ;; priority (1-based)
                   (let* ((priority-index (- (ash 2 depth) 1))
                          ;; highest priority base = width * (count-1)
                          ;; lowest priority base = 0
                          (priority-base (* (- count priority-index) width))
                          ;; 2^d nodes exist at depth = d
                          (priority-width (* width (ash 1 depth)))
                          (left (recurse (1+ depth))))
                     (declare ((integer 0 #.most-positive-fixnum)
                               priority-index priority-base priority-width))
                     (%make-inode initial-element
                                  (+ priority-base (random priority-width))
                                  :count (- (ash 1 (- max-depth depth)) 1)
                                  :accumulator initial-element
                                  :left left
                                  :right (recurse (1+ depth)))))))
      (recurse 0))))

(declaim (inline inode-ref))
(defun inode-ref (inode index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (assert (< index (inode-count inode)))
  (labels ((%ref (inode index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (let ((left-count (inode-count (%inode-left inode))))
               (cond ((< index left-count)
                      (%ref (%inode-left inode) index))
                     ((> index left-count)
                      (%ref (%inode-right inode) (- index left-count 1)))
                     (t (%inode-value inode))))
             (force-self inode)))
    (%ref inode index)))

(declaim (inline (setf inode-ref)))
(defun (setf inode-ref) (new-value inode index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (assert (< index (inode-count inode)))
  (labels ((%set (inode index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (let ((left-count (inode-count (%inode-left inode))))
               (cond ((< index left-count)
                      (%set (%inode-left inode) index))
                     ((> index left-count)
                      (%set (%inode-right inode) (- index left-count 1)))
                     (t (setf (%inode-value inode) new-value))))
             (force-self inode)))
    (%set inode index)
    new-value))

(declaim (inline inode-query))
(defun inode-query (inode l r)
  (declare ((integer 0 #.most-positive-fixnum) l r))
  (assert (< l r))
  (multiple-value-bind (inode-0-l inode-l-n)
      (inode-split inode l)
    (multiple-value-bind (inode-l-r inode-r-n)
        (inode-split inode-l-n (- r l))
      (prog1 (%inode-accumulator inode-l-r)
        (inode-merge inode-0-l (inode-merge inode-l-r inode-r-n))))))

(declaim (inline read-line-into))
(defun read-line-into (buffer-string &key (in *standard-input*) (terminate-char #\Space))
  (declare (simple-base-string buffer-string))
  (loop for c 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= c #\Newline)
        do (setf (schar buffer-string idx) c)
        finally (when (< idx (length buffer-string))
                  (setf (schar buffer-string idx) terminate-char))
                (return (values buffer-string 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

;; f(h[i]) = a[i] + max_{h < h[i] and h in h[0..i-1]}(f(h))
(defun main ()
  (let* ((n (read))
         (hs (make-array n :element-type 'uint31))
         (as (make-array n :element-type 'uint31))
         (buf (make-string 2200000 :element-type 'base-char))
         (dp (make-inode n 0)))
    (split-ints-into-vector (read-line-into buf) hs :key #'1-)
    (split-ints-into-vector (read-line-into buf) as)
    (dotimes (i n)
      (let ((h (aref hs i)))
        (setf (inode-ref dp h)
              (+ (aref as i)
                 (if (zerop h) 0 (inode-query dp 0 h))))))
    (println (inode-query dp 0 n))))

#-swank(main)


Measured memory_bytes: 55912