;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) 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)
  (defun %concat-name (&rest args)
    (if (cdr args)
        (format nil "~A-~A"
                (car args)
                (apply #'%concat-name (cdr args)))
        (car args)))

  (defun %concat+name+ (&rest args)
    (format nil "+~A+" (apply #'%concat-name args))))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defmacro define-cons-pack (name &rest slot-descriptions)
    (assert slot-descriptions () "~A has no slots." name)
    (labels ((extract-62bit-slots (list)
               (let ((position 0))
                 (loop for (slot-name slot-size) in list
                       while (<= (+ position slot-size) 62)
                       collect (list slot-name slot-size position)
                       do (incf position slot-size)))))
      (let* ((packer-name (intern (%concat-name "PACK" name)))
             (unpacker-macro-name (intern (%concat-name "WITH-UNPACKING" name)))
             (new-value (gensym "NEW-VALUE"))
             (tmp1 (gensym))
             (tmp2 (gensym))
             (tmp (gensym))
             (car-slots (extract-62bit-slots slot-descriptions))
             (car-revslots (reverse car-slots))
             (cdr-slots (extract-62bit-slots (nthcdr (length car-slots) slot-descriptions)))
             (cdr-revslots (reverse cdr-slots))
             (slots (append car-slots cdr-slots)))
        (assert (= (+ (length car-slots) (length cdr-slots))
                   (length slot-descriptions))
                () "Size restriction iviolated: each cell <= 62 bit, total size <= 124 bit")
        (unless (> (length cdr-slots) 0)
          (error "Whole size is too small. Use DEFINE-INTEGER-PACK instead."))
        (let ((car-width (+ (second (first car-revslots))
                            (third (first car-revslots))))
              (cdr-width (+ (second (first cdr-revslots))
                            (third (first cdr-revslots)))))
          `(progn
             (deftype ,name () '(cons (unsigned-byte ,car-width) (unsigned-byte ,cdr-width)))
             ;; define most positive integer for every slot as constant
             ,@(loop for (slot-name slot-size _) in slots
                     collect `(defconstant ,(intern (%concat+name+ "MAX" name slot-name))
                                (- (ash 1 ,slot-size) 1)))
             ;; setter and getter
             ,@(loop for slot in car-slots
                     for (slot-name slot-size slot-position) = slot
                     for accessor-name = (intern (%concat-name name slot-name))
                     append `((declaim (inline ,accessor-name (setf ,accessor-name)))
                              (defun ,accessor-name (,name)
                                (declare (type ,name ,name))
                                (ldb (byte ,slot-size ,slot-position)
                                     (the (unsigned-byte ,car-width) (car ,name))))
                              (defun (setf ,accessor-name) (,new-value ,name)
                                (declare (type ,name ,name))
                                (setf (ldb (byte ,slot-size ,slot-position)
                                           (the (unsigned-byte ,car-width) (car ,name)))
                                      ,new-value))))
             ,@(loop for slot in cdr-slots
                     for (slot-name slot-size slot-position) = slot
                     for accessor-name = (intern (%concat-name name slot-name))
                     append `((declaim (inline ,accessor-name (setf ,accessor-name)))
                              (defun ,accessor-name (,name)
                                (declare (type ,name ,name))
                                (ldb (byte ,slot-size ,slot-position)
                                     (the (unsigned-byte ,cdr-width) (cdr ,name))))
                              (defun (setf ,accessor-name) (,new-value ,name)
                                (declare (type ,name ,name))
                                (setf (ldb (byte ,slot-size ,slot-position)
                                           (the (unsigned-byte ,cdr-width) (cdr ,name)))
                                      ,new-value))))
             ;; constructor
             (declaim (inline ,packer-name))
             (defun ,packer-name ,(loop for slot in slots collect (car slot))
               (declare ,@(loop for (slot-name slot-size slot-position) in slots
                                collect `(type (unsigned-byte ,slot-size) ,slot-name)))
               (let ((,tmp1 ,(caar car-revslots))
                     (,tmp2 ,(caar cdr-revslots)))
                 (declare (type (unsigned-byte ,car-width) ,tmp1)
                          (type (unsigned-byte ,cdr-width) ,tmp2))
                 ,@(loop for (slot-name slot-size _) in (rest car-revslots)
                         collect `(setq ,tmp1 (+ ,slot-name
                                                 (the (unsigned-byte ,car-width)
                                                      (ash ,tmp1 ,slot-size)))))
                 ,@(loop for (slot-name slot-size _) in (rest cdr-revslots)
                         collect `(setq ,tmp2 (+ ,slot-name
                                                 (the (unsigned-byte ,cdr-width)
                                                      (ash ,tmp2 ,slot-size)))))
                 (cons ,tmp1 ,tmp2)))
             ;; destructuring-bind-style macro
             (defmacro ,unpacker-macro-name (vars ,name &body body)
               (check-type vars list)
               (assert (= (length vars) ,(length slots)))
               `(let* ((,',tmp ,,name)
                       (,',tmp1 (car ,',tmp))
                       (,',tmp2 (cdr ,',tmp)))
                  (declare (type (unsigned-byte ,,car-width) ,',tmp1)
                           (type (unsigned-byte ,,cdr-width) ,',tmp2))
                  (let* ,(loop for var in vars
                               for rest on ',car-slots
                               for (slot-name slot-size _) = (car rest)
                               collect `(,var
                                         (prog1 (the (unsigned-byte ,slot-size)
                                                     (ldb (byte ,slot-size 0) ,',tmp1))
                                           ,@(when (cdr rest)
                                               `((setq ,',tmp1 (ash ,',tmp1 ,(- slot-size))))))))
                    (let* ,(loop for var in (nthcdr ,(length car-slots) vars)
                                 for rest on ',cdr-slots
                                 for (slot-name slot-size _) = (car rest)
                                 collect `(,var
                                           (prog1 (the (unsigned-byte ,slot-size)
                                                       (ldb (byte ,slot-size 0) ,',tmp2))
                                             ,@(when (cdr rest)
                                                 `((setq ,',tmp2 (ash ,',tmp2 ,(- slot-size))))))))
                      ,@body))))))))))

(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 22 31 32 40 62 63 64)

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

;; Treap with implicit key for updating and querying interval.
(eval-when (:compile-toplevel :load-toplevel :execute)
  (define-cons-pack node (value- 40) (delta- 22) (value+ 40) (delta+ 22)))

(sb-int:defconstant-eqx +op-identity+
    (pack-node +max-node-value-+ +max-node-delta-+
               +max-node-value++ +max-node-delta++)
  #'equal)

(declaim (inline op))
(defun op (a b)
  (with-unpacking-node (a-value- a-delta- a-value+ a-delta+) a
    (with-unpacking-node (b-value- b-delta- b-value+ b-delta+) b
      (if (<= (- a-value- a-delta-) (- b-value- b-delta-))
          (if (<= (+ a-value+ a-delta+) (+ b-value+ b-delta+))
              (pack-node a-value- a-delta- a-value+ a-delta+)
              (pack-node a-value- a-delta- b-value+ b-delta+))
          (if (<= (+ a-value+ a-delta+) (+ b-value+ b-delta+))
              (pack-node b-value- b-delta- a-value+ a-delta+)
              (pack-node b-value- b-delta- b-value+ b-delta+))))))

(defconstant +updater-identity+ 0)

(declaim (inline updater-op))
(defun updater-op (a b)
  "Is the operator to compute and update LAZY value. A is the current LAZY value
and B is operand."
  (declare (uint40 a b))
  (+ a b))

(declaim (inline modifier-op))
(defun modifier-op (a b size)
  "Is the operator to update ACCUMULATOR (and VALUE) based on LAZY value. A is
the current ACCUMULATOR value and B is the LAZY value. SIZE is the length of the
specified interval."
  (declare (ignorable size))
  (with-unpacking-node (a-value- a-delta- a-value+ a-delta+) a
    (pack-node (min +max-node-value-+ (+ a-value- b))
               a-delta-
               (min +max-node-value++ (+ a-value+ b))
               a-delta+)))

(defstruct (itreap (:constructor %make-itreap (value priority &key left right (count 1) (accumulator value) (lazy +updater-identity+)))
                  (:copier nil)
                  (:conc-name %itreap-))
  (value +op-identity+ :type node)
  (accumulator +op-identity+ :type node)
  (lazy +updater-identity+ :type fixnum)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (count 1 :type (integer 0 #.most-positive-fixnum)) ; size of (sub)treap
  (left nil :type (or null itreap))
  (right nil :type (or null itreap)))

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

(declaim (inline itreap-accumulator))
(defun itreap-accumulator (itreap)
  (declare ((or null itreap) itreap))
  (if itreap
      (%itreap-accumulator itreap)
      +op-identity+))

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

(declaim (inline update-accumulator))
(defun update-accumulator (itreap)
  (declare (itreap itreap))
  (setf (%itreap-accumulator itreap)
        (if (%itreap-left itreap)
            (if (%itreap-right itreap)
                (let ((mid (op (%itreap-accumulator (%itreap-left itreap))
                               (%itreap-value itreap))))
                  (declare (dynamic-extent mid))
                  (op mid (%itreap-accumulator (%itreap-right itreap))))
                (op (%itreap-accumulator (%itreap-left itreap))
                    (%itreap-value itreap)))
            (if (%itreap-right itreap)
                (op (%itreap-value itreap)
                    (%itreap-accumulator (%itreap-right itreap)))
                (%itreap-value itreap)))))

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

(declaim (inline force-down))
(defun force-down (itreap)
  (declare (itreap itreap))
  (unless (eql +updater-identity+ (%itreap-lazy itreap))
    (when (%itreap-left itreap)
      (setf (%itreap-lazy (%itreap-left itreap))
            (updater-op (%itreap-lazy (%itreap-left itreap))
                        (%itreap-lazy itreap)))
      (setf (%itreap-accumulator (%itreap-left itreap))
            (modifier-op (%itreap-accumulator (%itreap-left itreap))
                         (%itreap-lazy itreap)
                         (%itreap-count (%itreap-left itreap)))))
    (when (%itreap-right itreap)
      (setf (%itreap-lazy (%itreap-right itreap))
            (updater-op (%itreap-lazy (%itreap-right itreap))
                        (%itreap-lazy itreap)))
      (setf (%itreap-accumulator (%itreap-right itreap))
            (modifier-op (%itreap-accumulator (%itreap-right itreap))
                         (%itreap-lazy itreap)
                         (%itreap-count (%itreap-right itreap)))))
    (setf (%itreap-value itreap)
          (modifier-op (%itreap-value itreap)
                       (%itreap-lazy itreap)
                       1))
    (setf (%itreap-lazy itreap) +updater-identity+)))

(defun itreap-split (itreap index)
  "Destructively splits the ITREAP into two nodes [0, INDEX) and [INDEX, N), where N
  is the number of elements of the ITREAP."
  (declare #.OPT ((integer 0 #.most-positive-fixnum) index))
  (unless (<= index (itreap-count itreap))
    (error 'invalid-itreap-index-error :index index :itreap itreap))
  (labels ((recur (itreap ikey)
             (unless itreap
               (return-from itreap-split (values nil nil)))
             (force-down itreap)
             (let ((left-count (itreap-count (%itreap-left itreap))))
               (if (<= ikey left-count)
                   (multiple-value-bind (left right)
                       (itreap-split (%itreap-left itreap) ikey)
                     (setf (%itreap-left itreap) right)
                     (force-self itreap)
                     (values left itreap))
                   (multiple-value-bind (left right)
                       (itreap-split (%itreap-right itreap) (- ikey left-count 1))
                     (setf (%itreap-right itreap) left)
                     (force-self itreap)
                     (values itreap right))))))
    (recur itreap index)))

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

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

(defun %heapify (top)
  "Properly swaps the priorities of the node and its two children."
  (declare #.OPT)
  (when top
    (let ((high-priority-node top))
      (when (and (%itreap-left top)
                 (> (%itreap-priority (%itreap-left top))
                    (%itreap-priority high-priority-node)))
        (setq high-priority-node (%itreap-left top)))
      (when (and (%itreap-right top)
                 (> (%itreap-priority (%itreap-right top))
                    (%itreap-priority high-priority-node)))
        (setq high-priority-node (%itreap-right top)))
      (unless (eql high-priority-node top)
        (rotatef (%itreap-priority high-priority-node)
                 (%itreap-priority top))
        (%heapify high-priority-node)))))

(defun make-itreap (size)
  "Makes a treap of SIZE in O(SIZE) time."
  (declare #.OPT)
  (labels ((build (l r)
             (declare ((integer 0 #.most-positive-fixnum) l r))
             (if (= l r)
                 nil
                 (let* ((mid (ash (+ l r) -1))
                        (node (%make-itreap (pack-node +max-node-value-+ mid
                                                       +max-node-value++ mid)
                                            (random most-positive-fixnum))))
                   (setf (%itreap-left node) (build l mid))
                   (setf (%itreap-right node) (build (+ mid 1) r))
                   (%heapify node)
                   (force-self node)
                   node))))
    (build 0 size)))

(defun (setf itreap-ref) (new-value itreap index)
  (declare #.OPT
           ((integer 0 #.most-positive-fixnum) index))
  (unless (< index (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index index))
  (labels ((%set (itreap index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (force-down itreap)
             (prog1
                 (let ((left-count (itreap-count (%itreap-left itreap))))
                   (cond ((< index left-count)
                          (%set (%itreap-left itreap) index))
                         ((> index left-count)
                          (%set (%itreap-right itreap) (- index left-count 1)))
                         (t (setf (%itreap-value itreap) new-value))))
               (force-self itreap))))
    (%set itreap index)
    new-value))

(defun itreap-map (function itreap)
  "Successively applies FUNCTION to ITREAP[0], ..., ITREAP[SIZE-1]."
  (declare #.OPT (function function))
  (when itreap
    (force-down itreap)
    (itreap-map function (%itreap-left itreap))
    (funcall function (%itreap-value itreap))
    (itreap-map function (%itreap-right itreap))
    (force-self itreap)))

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

(defconstant +mod+ 1000000007)

;; Body

;; (defun itreap-pprint (itreap)
;;   (write-char #\<)
;;   (itreap-map (lambda (x) (princ (caar x)) (write-char #\ )) itreap)
;;   (write-char #\>)
;;   (terpri))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (q (read))
         (a (- (read) 1))
         (b (- (read) 1))
         (xs (make-array q :element-type 'uint32))
         (itreap (make-itreap n)))
    (declare (uint32 n q a b))
    (dotimes (i q) (setf (aref xs i) (- (read-fixnum) 1)))
    (locally (declare (notinline pack-node))
      (setf (itreap-ref itreap a)
            (let ((value (abs (- (aref xs 0) b))))
              (pack-node value a value a))
            (itreap-ref itreap b)
            (let ((value (abs (- (aref xs 0) a))))
              (pack-node value b value b))))
    ;; #>itreap
    (do ((i 1 (+ i 1)))
        ((>= i q))
      (multiple-value-bind (itreap-l itreap-r) (itreap-split itreap (aref xs i))
        (let* ((left-query (itreap-accumulator itreap-l))
               (right-query (itreap-accumulator itreap-r))
               (value- (node-value- left-query))
               (delta- (node-delta- left-query))
               (value+ (node-value+ right-query))
               (delta+ (node-delta+ right-query))
               (new-value (min +max-node-value-+
                               (+ (- value- delta-) (aref xs i))
                               (- (+ value+ delta+) (aref xs i)))))
          (declare (uint40 value- value+ new-value)
                   (uint22 delta- delta+))
          (setf itreap (itreap-merge itreap-l itreap-r))
          (setf (%itreap-lazy itreap) (abs (- (aref xs (- i 1)) (aref xs i))))
          (force-down itreap)
          (force-self itreap)
          (setf (itreap-ref itreap (aref xs (- i 1)))
                (pack-node new-value (aref xs (- i 1))
                           new-value (aref xs (- i 1)))))))
    (let ((res most-positive-fixnum))
      (declare (uint62 res))
      (itreap-map (lambda (x) (setq res (min res (node-value- x)))) itreap)
      (println res))))

#-swank(main)


Measured memory_bytes: 112272