;; -*- 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
           #\# #\> (lambda (s c p) (declare (ignore c p)) (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
;;;
;;; Convex Hull Trick for monotone query (unfinished)
;;;

(deftype cht-element-type () 'fixnum)

(define-condition cht-empty-error (simple-error)
  ((cht :initarg :cht :accessor cht-empty-error-cht))
  (:report (lambda (condition stream)
             (format stream
                     "Attempted to get a value on an empty CHT ~W"
                     (cht-empty-error-cht condition)))))

(define-condition cht-full-error (simple-error)
  ((cht :initarg :cht :accessor cht-full-error-cht))
  (:report (lambda (condition stream)
             (format stream
                     "Attempted to push a value on a full CHT ~W"
                     (cht-full-error-cht condition)))))

(defstruct (convex-hull-trick
            (:constructor make-cht
                (max-length
                 &optional (minimum t)
                 &aux
                 (slopes (make-array max-length :element-type 'cht-element-type))
                 (intercepts (make-array max-length :element-type 'cht-element-type))))
            (:conc-name %cht-)
            (:copier nil))
  (slopes nil :type (simple-array cht-element-type (*)))
  (intercepts nil :type (simple-array cht-element-type (*)))
  (minimum t :type boolean)
  (start 0 :type (integer 0 #.most-positive-fixnum))
  (length 0 :type (integer 0 #.most-positive-fixnum))
  (max-length 0 :type (integer 0 #.most-positive-fixnum)))

;; four operations on deque
(declaim (inline %cht-pop-back))
(defun %cht-pop-back (cht)
  (decf (%cht-length cht)))

(declaim (inline %cht-pop-front))
(defun %cht-pop-front (cht)
  (decf (%cht-length cht))
  (incf (%cht-start cht))
  (when (= (%cht-start cht) (%cht-max-length cht))
    (setf (%cht-start cht) 0)))

(declaim (inline %cht-push-back))
(defun %cht-push-back (cht slope intercept)
  (let ((pos (+ (%cht-start cht) (%cht-length cht))))
    (declare ((integer 0 #.most-positive-fixnum) pos))
    (when (>= pos (%cht-max-length cht))
      (decf pos (%cht-max-length cht)))
    (setf (aref (%cht-slopes cht) pos) slope
          (aref (%cht-intercepts cht) pos) intercept)
    (incf (%cht-length cht))))

(declaim (inline %cht-push-front))
(defun %cht-push-front (cht slope intercept)
  (let ((new-start (- (%cht-start cht) 1)))
    (when (= -1 new-start)
      (incf new-start (%cht-max-length cht)))
    (setf (aref (%cht-slopes cht) new-start) slope
          (aref (%cht-intercepts cht) new-start) intercept)
    (setf (%cht-start cht) new-start)
    (incf (%cht-length cht))))

(declaim (inline %removable-p))
(defun %removable-p (slope1 intercept1 slope2 intercept2 slope3 intercept3)
  "Returns true iff the **second** line is removable."
  (>= (the cht-element-type (* (- intercept3 intercept2)
                               (- slope2 slope1)))
      (the cht-element-type (* (- intercept2 intercept1)
                               (- slope3 slope2)))))

;; NOTE: The slopes of lines newly added to CHT must be largest or smallest
;; ever.
(defun cht-push (cht slope intercept)
  "Adds a new line to CHT."
  (declare (optimize (speed 3))
           (cht-element-type slope intercept))
  (when (= (%cht-length cht) (%cht-max-length cht))
    (error 'cht-full-error :cht cht))
  (unless (%cht-minimum cht)
    (setq slope (- slope)
          intercept (- intercept)))
  (let ((slopes (%cht-slopes cht))
        (intercepts (%cht-intercepts cht)))
    (labels ((ref (i)
               (let ((pos (+ (%cht-start cht) i)))
                 (declare ((integer 0 #.most-positive-fixnum) pos))
                 (when (>= pos (%cht-max-length cht))
                   (decf pos (%cht-max-length cht)))
                 (values (aref slopes pos) (aref intercepts pos)))))
      (cond ((zerop (%cht-length cht))
             (%cht-push-front cht slope intercept))
            ((>= slope (aref slopes (%cht-start cht)))
             ;; push the line to the front if SLOPE is larger than that of the head.
             (loop for start = (%cht-start cht)
                   while (and (>= (%cht-length cht) 2)
                              (let ((slope+1 (aref slopes start))
                                    (intercept+1 (aref intercepts start)))
                                (multiple-value-bind (slope+2 intercept+2) (ref 1)
                                  (declare (cht-element-type slope+1 intercept+1 slope+2 intercept+2))
                                  (%removable-p slope intercept
                                                slope+1 intercept+1
                                                slope+2 intercept+2))))
                   do (%cht-pop-front cht)
                   finally (%cht-push-front cht slope intercept)))
            (t
             ;; push the line to the end if SLOPE is smaller than that of the tail.
             ;; TODO: assert it.
             (loop for offset = (%cht-length cht)
                   while (and (>= offset 2)
                              (multiple-value-bind (slope-2 intercept-2) (ref (- offset 2))
                                (multiple-value-bind (slope-1 intercept-1) (ref (- offset 1))
                                  (declare (cht-element-type slope-2 intercept-2 slope-1 intercept-1))
                                  (%removable-p slope-2 intercept-2
                                                slope-1 intercept-1
                                                slope intercept))))
                   do (%cht-pop-back cht)
                   finally (%cht-push-back cht slope intercept))))
      cht)))

(declaim (inline cht-get))
(defun cht-get (cht x)
  "Returns the minimum (maximum) value at X."
  (when (zerop (%cht-length cht))
    (error 'cht-empty-error :cht cht))
  (let ((ng -1)
        (ok (- (%cht-length cht) 1))
        (slopes (%cht-slopes cht))
        (intercepts (%cht-intercepts cht)))
    (declare ((integer -1 (#.array-total-size-limit)) ng ok))
    (labels ((calc (i)
               (let ((pos (+ (%cht-start cht) i)))
                 (declare ((integer 0 #.most-positive-fixnum) pos))
                 (when (>= pos (%cht-max-length cht))
                   (decf pos (%cht-max-length cht)))
                 (+ (* x (aref slopes pos))
                    (aref intercepts pos)))))
      (loop
        (when (<= (- ok ng) 1)
          (return
            (if (%cht-minimum cht)
                (calc ok)
                (- (calc ok)))))
        (let ((mid (ash (+ ng ok) -1)))
          (if (< (calc mid) (calc (+ mid 1)))
              (setq ok mid)
              (setq ng mid)))))))

(declaim (inline cht-increasing-get))
(defun cht-increasing-get (cht x)
  (when (zerop (%cht-length cht))
    (error 'cht-empty-error :cht cht))
  (let ((slopes (%cht-slopes cht))
        (intercepts (%cht-intercepts cht)))
    (labels ((calc (slope intercept)
               (declare (cht-element-type slope intercept))
               (+ (* x slope) intercept)))
      (loop while (and (>= (%cht-length cht) 2)
                       (let* ((pos (%cht-start cht))
                              (slope0 (aref slopes pos))
                              (intercept0 (aref intercepts pos)))
                         (incf pos)
                         (when (= pos (%cht-max-length cht))
                           (setq pos 0))
                         (let ((slope1 (aref slopes pos))
                               (intercept1 (aref intercepts pos)))
                           (>= (calc slope0 intercept0)
                               (calc slope1 intercept1)))))
            do (%cht-pop-front cht))
      (let ((start (%cht-start cht)))
        (if (%cht-minimum cht)
            (calc (aref slopes start) (aref intercepts start))
            (- (calc (aref slopes start) (aref intercepts start))))))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (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 #\-))
                                  (setf 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))))))))

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

(defun main ()
  (let* ((n (read))
         (c (read))
         (hs (make-array n :element-type 'uint31))
         (dp (make-array n :element-type 'uint62 :initial-element most-positive-fixnum))
         (cht (make-cht n)))
    (declare (uint62 n c))
    (dotimes (i n)
      (setf (aref hs i) (read-fixnum)))
    (setf (aref dp 0) 0)
    (loop for x from 1 below n
          do (cht-push cht
                       (* -2 (aref hs (- x 1)))
                       (+ (expt (aref hs (- x 1)) 2)
                          (aref dp (- x 1))))
             (let ((chtmin (cht-get cht (aref hs x))))
               (declare (fixnum chtmin))
               (setf (aref dp x)
                     (+ chtmin
                        c
                        (expt (aref hs x) 2)))))
    (println (aref dp (- n 1)))))

#-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:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+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 "")))

#+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 "5 6
1 2 3 4 5
"
    "20
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "2 1000000000000
500000 1000000
"
    "1250000000000
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "8 5
1 3 4 5 10 11 12 13
"
    "62
")))


Measured memory_bytes: 37608