(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
;; Treap accessible by index (O(log(n)))
(defstruct (treap (:constructor make-treap (key priority &key left right (count 1)))
                  (:copier nil)
                  (:conc-name %treap-))
  (key 0 :type fixnum)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (count 0 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null treap))
  (right nil :type (or null treap)))

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

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

(defun treap-bisect-left (value treap &key (test #'<))
  "Returns the smallest index and the corresponding key that satisfies
TREAP[index] >= VALUE. Returns the size of TREAP and VALUE if TREAP[size-1] <
VALUE."
  (declare #.OPT (function test))
  (labels ((recurse (count treap)
             (declare ((integer 0 #.most-positive-fixnum) count))
             (cond ((null treap) (values nil nil))
                   ((funcall test (%treap-key treap) value)
                    (recurse count (%treap-right treap)))
                   (t (let ((left-count (- count (treap-count (%treap-right treap)) 1)))
                        (multiple-value-bind (idx key)
                            (recurse left-count (%treap-left treap))
                          (if idx
                              (values idx key)
                              (values left-count (%treap-key treap)))))))))
    (declare (ftype (function * (values t t &optional)) recurse))
    (multiple-value-bind (idx key)
        (recurse (treap-count treap) treap)
      (if idx
          (values idx key)
          (values (treap-count treap) value)))))

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

(declaim (inline treap-insert))
(defun treap-insert (key treap &key (test #'<))
  "Destructively inserts KEY into TREAP and returns the result treap. You cannot
rely on the side effect. Use the returned value.

The behavior is undefined when duplicated keys are inserted."
  (declare ((or null treap) treap)
           (function test))
  (labels ((recurse (node treap)
             (declare (treap node))
             (cond ((null treap) node)
                   ((> (%treap-priority node) (%treap-priority treap))
                    (setf (values (%treap-left node) (%treap-right node))
                          (treap-split (%treap-key node) treap :test test))
                    (update-count node)
                    node)
                   (t
                    (if (funcall test (%treap-key node) (%treap-key treap))
                        (setf (%treap-left treap)
                              (recurse node (%treap-left treap)))
                        (setf (%treap-right treap)
                              (recurse node (%treap-right treap))))
                    (update-count treap)
                    treap))))
    (recurse (make-treap key (random most-positive-fixnum)) treap)))

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

(declaim (inline treap-ref))
(defun treap-ref (treap index)
  (declare #.OPT ; TCO
           ((or null treap) treap)
           ((integer 0 #.most-positive-fixnum) index))
  (when (>= index (treap-count treap))
    (error (make-condition 'invalid-treap-index-error :treap treap :index index)))
  (labels ((%ref (treap index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (let ((left-count (treap-count (%treap-left treap))))
               (cond ((< index left-count)
                      (%ref (%treap-left treap) index))
                     ((> index left-count)
                      (%ref (%treap-right treap) (- index left-count 1)))
                     (t (%treap-key treap))))))
    (%ref treap index)))

(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 (when (< ,idx ,buffer-size)
                       (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

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (as (make-array n :element-type 'uint32))
         (positions (make-array (1+ n) :element-type 'uint32))
         (treap nil))
    (declare ((integer 1 200000) n))
    (split-ints-into-vector (buffered-read-line 1400000) as)
    (dotimes (i n)
      (setf (aref positions (aref as i)) i))
    (println
     (loop for a from 1 to n
           for pos of-type (integer 0 200000) = (aref positions a)
           sum (multiple-value-bind (r-idx r-value)
                   (treap-bisect-left pos treap)
                 (declare ((integer 0 200000) r-idx r-value))
                 (when (= r-idx (treap-count treap))
                   (setf r-value n))
                 (let ((l-value (if (= r-idx 0)
                                    -1
                                    (treap-ref treap (- r-idx 1)))))
                   (declare ((integer -1 200000) l-value))
                   (prog1 (* a
                             (max 1 (- r-value pos))
                             (max 1 (- pos l-value)))
                     (setf treap (treap-insert pos treap)))))
           of-type fixnum))))

#-swank(main)


Measured memory_bytes: 54760