Problem:
 Score : 700 points    Problem Statement Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1) .  Now, he will perform the following operation exactly once :   Choose K consecutive elements in P and sort them in ascending order.   Find the number of permutations that can be produced as P after the operation.      Constraints  2 \leq N \leq 200000  2 \leq K \leq N  0 \leq P_i \leq N-1  P_0,P_1,\cdots,P_{N-1} are all different.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  P_0  P_1  \cdots  P_{N-1}       Output Print the number of permutations that can be produced as P after the operation.        Sample Input 1 5 3
0 2 1 4 3      Sample Output 1 2  Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4) .       Sample Input 2 4 4
0 1 2 3      Sample Output 2 1       Sample Input 3 10 4
2 0 1 3 7 5 4 6 8 9      Sample Output 3 6

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
from heapq import heappop,heappush,heapify


import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()

  def insert(self,x):
    heapq.heappush(self.p, x)
    return

  def erase(self,x):
    heapq.heappush(self.q, x)
    return

  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else None
minheap=pqheap()
maxheap=pqheap()
for i in range(k):
  minheap.insert(p[i])
  maxheap.insert(-p[i])
ans=1
premin=minheap.minimum()
premax=-maxheap.minimum()

for i in range(k,n):
  ins=p[i]
  era=p[i-k]
  minheap.erase(era)
  maxheap.erase(-era)
  minheap.insert(ins)
  maxheap.insert(-ins)
  if premin==era and ins==-maxheap.minimum():
    pass
  else:
    ans+=1
  premax=-maxheap.minimum()
  premin=minheap.minimum()
ans0=0
now=1
pre=p[0]
for x in p[1:]:
  if x>pre:
    now+=1
  else:
    now=1
  if now==k:
    ans0+=1
  pre=x


print(ans-max(0,ans0-1))

Solution (Python):
class SegTree:
    """ define what you want to do with 0 index, ex) size = tree_size, func = min or max, sta = default_value """
    
    def __init__(self,size,func,sta):
        self.n = size
        self.size = 1 << size.bit_length()
        self.func = func
        self.sta = sta
        self.tree = [sta]*(2*self.size)

    def build(self, list):
        """ set list and update tree"""
        for i,x in enumerate(list,self.size):
            self.tree[i] = x

        for i in range(self.size-1,0,-1):
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    def set(self,i,x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i<<1],self.tree[i<<1 | 1])

    
    def get(self,l,r):
        """ take the value of [l r) with func (min or max)"""
        l += self.size
        r += self.size
        res = self.sta

        while l < r:
            if l & 1:
                res = self.func(self.tree[l],res)
                l += 1
            if r & 1:
                res = self.func(self.tree[r-1],res)
            l >>= 1
            r >>= 1
        return res

n,k = map(int,input().split())
p = list(map(int,input().split()))

segmin = SegTree(n,min,10**18)
segmax = SegTree(n,max,-1)
segmin.build(p)
segmax.build(p)

count = [1]*n
for i in range(1,n):
    if p[i] > p[i-1]:
        count[i] = count[i-1]+1
if n == k or max(count) == n:
    print(1)
    exit()
ans = 1
check = False
if count[k-1] == k:
    check = True
for i in range(k,n):
    if count[i] >= k:
        if check:
            continue
        else:
            check = True
            ans += 1
            continue
    elif segmin.get(i-k,i+1) == p[i-k] and segmax.get(i-k,i+1) == p[i]:
        continue
    ans += 1

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


N, K = MAP()
P = LIST()

check = [0]*(N-K+1)
up_check = [0]*N
for i in range(1, N):
	if P[i] >= P[i-1]:
		up_check[i] = 1

up_check_acc = list(accumulate(up_check))
for i in range(N-K+1):
	if up_check_acc[i+K-1]-up_check_acc[i] == K-1:
		check[i] = 1

q1 = sorted((P[:K]))
q2 = [N]
q3 = sorted([-x for x in P[:K]])
q4 = [N]

ans = N-K+1
for i, p in enumerate(P[K:]):
	heappush(q1, p)
	heappush(q3, -p)
	while q1[0] == q2[0]:
		heappop(q1)
		heappop(q2)

	while q3[0] == q4[0]:
		heappop(q3)
		heappop(q4)

	if q1[0] == P[i] and q3[0] == -p and check[i]*check[i+1] == 0:
		ans -= 1

	heappush(q2, P[i])
	heappush(q4, -P[i])

ans -= max(0, sum(check)-1)
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
Ps = list(mapint())

def segfunc(x, y):
    return min(x, y)

def segfunc_2(x, y):
    return max(x, y)

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

if N==K:
    print(1)
    exit()
seg_min = SegTree(Ps, segfunc, 10**18)
seg_max = SegTree(Ps, segfunc_2, -1)

str_set = set()
cnt = 1
old = 10**18
is_increase = [0]*N
for i in range(N):
    p = Ps[i]
    if p>old:
        cnt += 1
        is_increase[i] = cnt
    else:
        cnt = 1
        is_increase[i] = cnt
    old = p

original = 0
ans = N-K+1
for i in range(N-K):
    mini = Ps[i]
    maxi = Ps[i+K]
    if is_increase[i+K-1]>=K:
        original = 1
        ans -= 1
    elif (seg_min.query(i, i+K+1)==mini and seg_max.query(i, i+K+1)==maxi):
        ans -= 1
if is_increase[-1]>=K:
    original = 1
    ans -= 1
print(ans+original)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,K = LI()
    P = LI()

    N0 = 2 ** (N.bit_length())
    st1 = [0] * (2 * N0)
    st2 = [0] * (2 * N0)

    i = N0-1
    for x in P:
        st1[i] = st2[i] = x
        i += 1


    for i in range(N0-2,-1,-1):
        st1[i] = max(st1[i*2+1],st1[i*2+2])
        st2[i] = min(st2[i*2+1],st2[i*2+2])

    def query_max(l, r):
        L = l + N0;
        R = r + N0
        ret = 0
        while L < R:
            if L % 2:
                ret = max(ret, st1[L - 1])
                L += 1
            if R % 2:
                R -= 1
                ret = max(ret, st1[R - 1])
            L //= 2;
            R //= 2
        return ret


    def query_min(l, r):
        L = l + N0;
        R = r + N0
        ret = N + 1  
        while L < R:
            if L % 2:
                ret = min(ret, st2[L - 1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret, st2[R - 1])
            L //= 2;
            R //= 2
        return ret


    ans = 0
    cnt = 0
    flg = 0
    bp = N
    for i in range(N):
        if P[i] > bp:
            cnt += 1
        else:
            cnt = 0
        bp = P[i]

        if i < K - 1: continue

        if cnt >= K-1:
            flg = 1
        elif i >= K and query_min(i-K,i) == P[i-K] and query_max(i-K+1,i+1) == P[i]:
            pass
        else:
            ans += 1

    print(ans+flg)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    S = [] 
    T = [] 
    D = deque()
    C = 0 

    for k in range(K):
        a = A[k]
        heapq.heappush(S, (a, k))
        heapq.heappush(T, (-a, k))
        if k > 0:
            c = 1 if A[k - 1] > A[k] else 0
            D.append(c)
            C += c

    r = 0
    F = True if C == 0 else False
    res = 0 if F else 1

    
    
    
    for i in range(N - K):
        
        C -= D.popleft()
        c = 1 if A[K + i - 1] > A[K + i] else 0
        D.append(c)
        C += c

        out_a = A[i]
        in_a = A[K + i]
        
        
        heapq.heappush(T, (-in_a, K + i))
        while T[0][1] <= i:
            heapq.heappop(T)

        if C == 0:
            F = True
        else:
            if not (T[0][0] == -in_a and S[0][0] == out_a):
                res += 1

        
        
        heapq.heappush(S, (in_a, K + i))
        while S[0][1] <= i:
            heapq.heappop(S)
        
        
       
        
    if F:
        res += 1
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
def segfunc_min(x,y):return min(x,y)
def segfunc_max(x,y):return max(x,y)
ide_ele_min=10**18
ide_ele_max=0
class segtree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,k=map(int,input().split())
*p,=map(int,input().split())
q=[1]*n
ans=n-k+1
cnt=1
c=0
for i in range(n-1):
  if p[i+1]>p[i]:cnt+=1
  else:cnt=1
  c+=cnt>=k
  if cnt>k:q[i-k+1]=0
if c>1:ans-=c-1
stn=segtree(p,segfunc_min,ide_ele_min)
stx=segtree(p,segfunc_max,ide_ele_max)
for i in range(n-k):
  if stn.query(i,i+k)==p[i] and stx.query(i+1,i+k+1)==p[i+k] and q[i]:ans-=1
print(ans)

Solution (Python):
import heapq


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    ans = 1
    inside_que = [0] * N
    min_que, max_que = [], []
    for i in range(K):
        heapq.heappush(min_que, P[i])
        heapq.heappush(max_que, - P[i])
        inside_que[P[i]] = 1
    for i in range(N - K):
        old_p, new_p = P[i], P[i + K]
        if not(old_p == min_que[0] and new_p >= - max_que[0]):
            ans += 1
        inside_que[old_p] = 0
        inside_que[new_p] = 1
        heapq.heappush(min_que, new_p)
        heapq.heappush(max_que, - new_p)
        while inside_que[min_que[0]] == 0:
            heapq.heappop(min_que)
        while inside_que[-max_que[0]] == 0:
            heapq.heappop(max_que)
    desc_index = 0
    exists_asc_section = False
    for i in range(1, N):
        if P[i - 1] > P[i]:
            if i - desc_index >= K:
                ans -= 1
                exists_asc_section = True
            desc_index = i
    if N - desc_index >= K:
        exists_asc_section = True
        ans -= 1
    if exists_asc_section:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))

    seg_min = SegTree(P, lambda x, y: min(x, y), f_inf)
    seg_max = SegTree(P, lambda x, y: max(x, y), -f_inf)
    mi = seg_min.query(0, k)
    ma = seg_max.query(0, k)
    res = {(0, k - 1)}
    for i in range(1, n - k + 1):
        prev = P[i - 1]
        new = P[i + k - 1]
        if prev != mi or new < ma:
            res.add((i, i + k - 1))
        mi = seg_min.query(i, i + k)
        ma = seg_max.query(i, i + k)

    ascending = []
    head = 0
    foot = 1
    cnt = 1
    for i in range(1, n):
        if P[i - 1] < P[i]:
            cnt += 1
            foot = i
        else:
            cnt = 1
            head = i
        if cnt == k:
            ascending.append((head, foot))
            head = i
            cnt -= 1

    ans = len(res)
    flg = False
    for section in ascending:
        if section in res:
            if not flg:
                flg = True
            else:
                ans -= 1
    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
class SegTreeMax():
    def segfunc(self, x, y):
        if x > y:
            return x
        else:
            return y

    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segfunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segfunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segfunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segfunc(res, self.seg[begin])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
        return res

class SegTreeMin():
    def segfunc(self, x, y):
        if x < y:
            return x
        else:
            return y

    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segfunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segfunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segfunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segfunc(res, self.seg[begin])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
        return res

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    csum = [0]*n
    for i in range(1, n):
        csum[i] += csum[i-1]
        if p[i-1] > p[i]:
            csum[i] += 1
    seg_max = SegTreeMax(-float("inf"), p)
    seg_min = SegTreeMin( float("inf"), p)
    ans = 0
    f = True
    for i in range(k-1, n):
        if csum[i-k+1] == csum[i]:
            if f:
                ans += 1
                f = False
        elif k <= i and not(p[i-k] == seg_min.query(i-k, i) and p[i] == seg_max.query(i-k+1, i+1)):
            ans += 1
        elif i == k-1 and csum[i-k+1] < csum[i]:
            ans += 1
        
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])


import sys
input = sys.stdin.readline


N, K = map(int, input().split())
P = list(map(int, input().split()))
e = float("inf")
op = lambda x, y : x if x < y else y
st1 = SegmentTree(N, op, e)
st1.built(P)
e = 0
op = lambda x, y : x if x > y else y
st2 = SegmentTree(N, op, e)
st2.built(P)

Q = [1]
for i in range(N-1):
    if P[i] < P[i+1]:
        Q.append(Q[-1]+1)
    else:
        Q.append(1)

res, flg = 1, 0
if Q[K-1]>=K:
    flg = 1
for i in range(1,N-K+1):
    mi, ma = st1.get(i,i+K-1), st2.get(i,i+K-1)
    if (P[i+K-1] < ma or P[i-1] > mi):
        if Q[i+K-1]<K:
            res += 1
        elif not flg:
            res += 1
            flg = 1
print(res)

Solution (Python):
class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。(ただし単位元は添加可能)
    """
    @classmethod
    def all_identity(cls, operator, identity, size):
        return cls(operator, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, identity, data)

    
    def __init__(self, operator, identity, data):
        self.op = operator
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        while i:
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def solve(K,P):
    N = len(P)
    maxseg = SegmentTree.from_initial_data(max2, -1, P)
    minseg = SegmentTree.from_initial_data(min2, N, P)

    delta = [b-a for a,b in zip(P,P[1:])]
    deltaseg = SegmentTree.from_initial_data(min2, N, delta)

    c = 1
    sorted_ever_counted = deltaseg[:K-1] > 0
    for i in range(N-K):
        a = maxseg[i+1:i+K]
        b = minseg[i+1:i+K]
        is_sorted = deltaseg[i+1:i+K] > 0

        if b < P[i] or a > P[i+K]:
            if is_sorted:
                c += int(not sorted_ever_counted)
                sorted_ever_counted = True
            else:
                c += 1

    return c

if __name__ == '__main__':
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    print(solve(K,P))

Solution (Python):
import math
import numpy as np
import decimal
import collections
import itertools
import sys

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = 0
par = [-1 for i in range(n)]


def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True

mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)

BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
li = [1 for i in range(n - k + 1)]
for i in range(1, k):
    if p[i - 1] > p[i]:
        cnt += 1
if cnt == 0:
    li[0] = 0
for i in range(k, n):
    if p[i - 1] > p[i]:
        cnt += 1
    if p[i - k] > p[i - k + 1]:
        cnt -= 1
    if cnt == 0:
        li[i - k + 1] = 0
Q1 = deque([])
Q2 = deque([])
L1 = [0 for i in range(n - k + 2)]
L2 = [0 for i in range(n - k + 2)]
for i in range(n):
    while Q1 and p[Q1[-1]] > p[i]:
        Q1.pop()
    while Q2 and p[Q2[-1]] < p[i]:
        Q2.pop()
    Q1.append(i)
    Q2.append(i)
    if Q1[0] == i - k + 1:
        Q1.popleft()
    if Q2[0] == i - k + 1:
        Q2.popleft()
    if i >= k - 2:
        L1[i - k + 2] = p[Q1[0]]
        L2[i - k + 2] = p[Q2[0]]
ans = 0
for i in range(1, n - k + 1):
    if p[i - 1] > L1[i] or p[i + k - 1] < L2[i]:
        if li[i] > 0:
            ans += 1
print(ans - min(li) + li[0] + 1)

Solution (Python):
import sys
from heapq import *
input = sys.stdin.readline


def solve(n, k, p):
    res = n-k+1
    count = 0
    length = 1
    
    judge_max = [-x for x in p[:k]]
    judge_min = p[:k]
    heapify(judge_max)
    heapify(judge_min)
    already = [False]*n
    
    for i in range(k-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
            
    if length == k:
        count += 1
    
    for i in range(k-1, n-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
        
        already[p[i-k+1]] = True
        while True:
            vmax = -judge_max[0]
            if already[vmax]:
                heappop(judge_max)
                continue
            else:
                break
        while True:
            vmin = judge_min[0]
            if already[vmin]:
                heappop(judge_min)
                continue
            else:
                break
        if p[i-k+1] < vmin and vmax < p[i+1]:
            res -= 1
        
        elif length >= k:
            if count:
                res -= 1
            count += 1
        heappush(judge_max, -p[i+1])
        heappush(judge_min, p[i+1])
    
    return res

    
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    ans = solve(n, k, p)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    from collections import deque
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))

    if N == K:
        return print(1)

    p_min = [0] * (N - K)
    p_max = [0] * (N - K)
    p_asc = [0] * (N - K + 1)

    def calc_min():
        que = deque()
        que.append(P[0])

        for i in range(1, K + 1):
            cur = P[i]
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
        p_min[0] = que[0]

        for i in range(N - K - 1):
            prev = P[i]
            cur = P[i + K + 1]
            if que[0] == prev:
                que.popleft()
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
            p_min[i + 1] = que[0]

    def calc_max():
        que = deque()
        que.append(P[0])

        for i in range(1, K + 1):
            cur = P[i]
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
        p_max[0] = que[0]

        for i in range(N - K - 1):
            prev = P[i]
            cur = P[i + K + 1]
            if que[0] == prev:
                que.popleft()
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
            p_max[i + 1] = que[0]

    def calc_asc():
        prev = -1
        cnt = 0
        for i in range(K):
            cur = P[i]
            if prev < cur:
                cnt += 1
            else:
                cnt = 1
            prev = cur
        p_asc[0] = cnt

        for i in range(N - K):
            cur = P[i + K]
            if prev < cur:
                p_asc[i + 1] = min(p_asc[i] + 1, K)
            else:
                p_asc[i + 1] = 1
            prev = cur

    calc_min()
    calc_max()
    calc_asc()

    uf = UnionFind(N - K + 1)

    asc_list = []
    for i in range(N - K + 1):
        if p_asc[i] == K:
            asc_list.append(i)
    if len(asc_list) > 1:
        for i in range(1, len(asc_list)):
            uf.union(asc_list[0], asc_list[i])

    for i in range(N - K):
        if p_min[i] == P[i] and p_max[i] == P[i + K]:
            uf.union(i, i + 1)

    print(uf.group_count())


if __name__ == '__main__':
    main()