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

(setf *print-circle* t)

;; Treap with implicit key for updating and querying interval.

(defconstant +inf+ #xFFFFFFFFFF)
(sb-int:defconstant-eqx +op-identity+
    (cons +inf+ +inf+)
  #'equal)

(declaim (inline op))
(defun op (a b)
  (let* ((a- (car a))
         (a+ (cdr a))
         (b- (car b))
         (b+ (cdr b))
         (a-value- (ldb (byte 40 0) a-))
         (a-delta- (ldb (byte 22 40) a-))
         (a-value+ (ldb (byte 40 0) a+))
         (a-delta+ (ldb (byte 22 40) a+))
         (b-value- (ldb (byte 40 0) b-))
         (b-delta- (ldb (byte 22 40) b-))
         (b-value+ (ldb (byte 40 0) b+))
         (b-delta+ (ldb (byte 22 40) b+)))
    (declare (uint62 a- a+ b- b+)
             (uint40 a-value- a-value+ b-value- b-value+)
             (uint22 a-delta- b-delta- a-delta+ b-delta+))
    (cons (if (<= (- a-value- a-delta-) (- b-value- b-delta-))
              (dpb a-delta- (byte 22 40) a-value-)
              (dpb b-delta- (byte 22 40) b-value-))
          (if (<= (+ a-value+ a-delta+) (+ b-value+ b-delta+))
              (dpb a-delta+ (byte 22 40) a-value+)
              (dpb b-delta+ (byte 22 40) b-value+)))))

(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))
  (let* ((a- (car a))
         (a+ (cdr a))
         (a-value- (ldb (byte 40 0) a-))
         (a-delta- (ldb (byte 22 40) a-))
         (a-value+ (ldb (byte 40 0) a+))
         (a-delta+ (ldb (byte 22 40) a+)))
    (declare (uint62 a- a+)
             (uint40 a-value- a-value+ b)
             (uint22 a-delta- a-delta+))
    (cons (dpb a-delta- (byte 22 40) (min +inf+ (+ a-value- b)))
          (dpb a-delta+ (byte 22 40) (min +inf+ (+ a-value+ b))))))

(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 (cons uint62 uint62))
  (accumulator +op-identity+ :type (cons uint62 uint62))
  (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 (cons (dpb mid (byte 22 40) +inf+)
                                                  (dpb mid (byte 22 40) +inf+))
                                            (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)))
    (setf (itreap-ref itreap a)
          (let ((value (abs (- (aref xs 0) b))))
            (cons (dpb a (byte 22 40) value) (dpb a (byte 22 40) value)))
          (itreap-ref itreap b)
          (let ((value (abs (- (aref xs 0) a))))
            (cons (dpb b (byte 22 40) value) (dpb b (byte 22 40) value))))
    ;; #>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- (ldb (byte 40 0) (the uint62 (car left-query))))
               (delta- (ldb (byte 22 40) (the uint62 (car left-query))))
               (value+ (ldb (byte 40 0) (the uint62 (cdr right-query))))
               (delta+ (ldb (byte 22 40) (the uint62 (cdr right-query))))
               (new-value (min +inf+
                               (+ (- 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)))
                (cons (dpb (aref xs (- i 1)) (byte 22 40) new-value)
                      (dpb (aref xs (- i 1)) (byte 22 40) new-value))))))
    (let ((res most-positive-fixnum))
      (declare (uint62 res))
      (itreap-map (lambda (x) (setq res (min res (ldb (byte 40 0) (car x))))) itreap)
      (println res))))

#-swank(main)


Measured memory_bytes: 111336