;; -*- 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
;;;
;;; ARRAY-ELEMENT-TYPE is not constant-folded on SBCL version earlier than
;;; 1.5.0. See
;;; https://github.com/sbcl/sbcl/commit/9f0d12e7ab961828931d01c0b2a76a5885ad35d2
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:deftransform array-element-type ((array))
    (let ((type (sb-c::lvar-type array)))
      (flet ((element-type (type)
               (and (sb-c::array-type-p type)
                    (sb-int:neq (sb-kernel::array-type-specialized-element-type type) sb-kernel:*wild-type*)
                    (sb-kernel:type-specifier (sb-kernel::array-type-specialized-element-type type)))))
        (cond ((let ((type (element-type type)))
                 (and type
                      `',type)))
              ((sb-kernel:union-type-p type)
               (let (result)
                 (loop for type in (sb-kernel:union-type-types type)
                       for et = (element-type type)
                       unless (and et
                                   (if result
                                       (equal result et)
                                       (setf result et)))
                       do (sb-c::give-up-ir1-transform))
                 `',result))
              ((sb-kernel:intersection-type-p type)
               (loop for type in (sb-kernel:intersection-type-types type)
                     for et = (element-type type)
                     when et
                     return `',et
                     finally (sb-c::give-up-ir1-transform)))
              (t
               (sb-c::give-up-ir1-transform)))))))

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

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

(declaim (inline make-slide-opt-table))
(defun make-slide-opt-table (vector width order)
  "Computes all the minima (or maxima) of the subsequences of the given width,
VECTOR[i, i+WIDTH), in O(n). Return a vector, whose i-th element is the
minimum (or maximum) of the subsequence beginning with the index i.

ORDER := strict order (#'< corresponds to slide min. and #'> to slide max.)"
  (declare (vector vector)
           ((integer 1 #.most-positive-fixnum) width))
  (let* ((n (length vector))
         (deq (make-array n :element-type '(integer 0 #.most-positive-fixnum)))
         (front-pos 0)
         (end-pos -1)
         (l 0)
         (r 0)
         (res (make-array (+ 1 (- n width)) :element-type (array-element-type vector))))
    (declare ((integer -1 #.most-positive-fixnum) front-pos end-pos l r))
    (assert (<= width n))
    (labels ((push-back (x)
               (incf end-pos)
               (setf (aref deq end-pos) x))
             (pop-back ()
               (decf end-pos))
             (pop-front ()
               (incf front-pos))
             (peek-back ()
               (aref deq end-pos))
             (peek-front ()
               (aref deq front-pos))
             (extend ()
               (loop while (and (<= front-pos end-pos)
                                (not (funcall order
                                              (aref vector (peek-back))
                                              (aref vector r))))
                     do (pop-back))
               (push-back r)
               (incf r))
             (shrink ()
               (when (= (aref deq front-pos) l)
                 (pop-front))
               (incf l)))
      (declare (inline push-back pop-back pop-front peek-back peek-front))
      (loop for i below width
            do (extend))
      (loop for i from width below n
            do (setf (aref res (- i width))
                     (aref vector (peek-front)))
               (extend)
               (shrink)
            finally (setf (aref res (- i width))
                          (aref vector (peek-front))))
      res)))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (k (read))
         (ps (make-array n :element-type 'uint32))
         (ascending? (make-array (+ 1 (- n k)) :element-type 'bit :initial-element 0)))
    (declare (uint31 n k))
    (dotimes (i n)
      (setf (aref ps i) (read-fixnum)))
    (let ((streak 1))
      (declare (uint31 streak))
      (loop for i from 1 below n
            do (if (< (aref ps (- i 1)) (aref ps i))
                   (incf streak)
                   (setq streak 1))
               (when (>= streak k)
                 (setf (aref ascending? (+ 1 (- i k))) 1))))
    (let ((mintable (make-slide-opt-table ps k #'<))
          (maxtable (make-slide-opt-table ps k #'>))
          (original 0)
          (res 0))
      (declare (uint62 res original))
      (dotimes (init (+ 1 (- n k)))
        (cond ((= 1 (aref ascending? init))
               (setq original 1))
              ((zerop init)
               (incf res))
              ((and (= (aref ps (- init 1))
                       (aref mintable (- init 1)))
                    (= (aref ps (+ init k -1))
                       (aref maxtable init)))
               ;; do nothing
               )
              (t
               (incf res))))
      (println (+ res original)))))

#-swank (main) 


Measured memory_bytes: 35300