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):
class SegTree:  
    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)



n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

asc_count = [1] * n
for i in range(1, n):
    if P[i] > P[i - 1]:
        asc_count[i] = asc_count[i - 1] + 1

ans = 1
no_count = 0
if asc_count[k - 1] >= k:
    no_count += 1
for i in range(1, n - k + 1):
    if P[i - 1] != min_seg.query(i - 1, i + k - 1) or P[i + k - 1] != max_seg.query(i, i + k):
        ans += 1
        if asc_count[i + k - 1] >= k:
            no_count += 1

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

Solution (Python):
class SegTree:  
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

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



n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

asc_count = [1] * n
for i in range(1, n):
    if P[i] > P[i - 1]:
        asc_count[i] = asc_count[i - 1] + 1

ans = 0
no_count = 0
min_out_flag = False
for i in range(n - k + 1):
    if not min_out_flag or P[i + k - 1] != max_seg.query(i, i + k):
        ans += 1
        if asc_count[i + k - 1] >= k:
            no_count += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False
print(ans - max(no_count - 1, 0))

Solution (Python):
from collections import Counter, deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1



LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1
LIS = LIS[:N - K + 1]


def slide_min(A, K):
    deq, ret = deque([]), []
    for k in range(len(A)):
        while deq and A[deq[-1]] >= A[k]:
            deq.pop()
        deq.append(k)

        if k < K - 1:
            continue

        if deq[0] + K <= k:
            deq.popleft()
        ret.append(A[deq[0]])

    return ret



MIN = slide_min(P, K)
MAX = list(map(lambda x: -x, slide_min(list(map(lambda x: -x, P)), K)))


for i in range(N - K + 1):
    flg = False
    if LIS[i] >= K:
        flg = True

    if (i + 1 < N - K + 1) and (P[i] == MIN[i]) and (P[i + K] == MAX[i + 1]):
        flg = True

    ans -= flg

if len([l for l in LIS if l >= K]):
    ans += 1
print(ans)

Solution (Python):
from collections import Counter, deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1



LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1
LIS = LIS[:N - K + 1]



slide_min = deque([])
MIN = []
for k in range(N):
    while slide_min and P[slide_min[-1]] >= P[k]:
        slide_min.pop()
    slide_min.append(k)

    if k < K - 1:
        continue

    if slide_min[0] + K <= k:
        slide_min.popleft()
    MIN.append(P[slide_min[0]])



slide_max = deque([])
MAX = []
for k in range(N):
    while slide_max and P[slide_max[-1]] <= P[k]:
        slide_max.pop()
    slide_max.append(k)

    if k < K - 1:
        continue

    if slide_max[0] + K <= k:
        slide_max.popleft()
    MAX.append(P[slide_max[0]])


for i in range(N - K + 1):
    flg = False
    if LIS[i] >= K:
        flg = True

    if (i + 1 < N - K + 1) and (P[i] == MIN[i]) and (P[i + K] == MAX[i + 1]):
        flg = True

    ans -= flg

if len([l for l in LIS if l >= K]):
    ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


class SegmentTreeRMQ(object):  
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        
        self.array = [value] * (2 * self.len)

    def update(self, i, x):  
        i += self.len
        while i > 0:
            self.array[i] = min(self.array[i], x)
            i >>= 1
        

    def get(self, i):  
        return self.array[i + self.len]

    def get_minimum(self, l, r):  
        L = l+self.len
        R = r+self.len
        ANS = 1 << 30

        while L < R:
            if L & 1:
                ANS = min(ANS, self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = min(ANS, self.array[R])
            L >>= 1
            R >>= 1

        return ANS


N, K = na()
P = na()

if N == K or N == 2:
    print(1)
    exit()


min_tree = SegmentTreeRMQ(N, N)
max_tree = SegmentTreeRMQ(N, 1)

for i, p in enumerate(P):
    min_tree.update(i, p)
    max_tree.update(i, -p)

no_change = [0] * (N-K+1)

last = -1

for i in range(N):
    if i - last >= K:
        no_change[i-K+1] = 1
    if i == N-1:
        break
    if P[i] > P[i+1]:
        last = i




ans = 1
no_count = 0

for i in range(N-K):
    if P[i] > min_tree.get_minimum(i+1, i+K+1) or -P[i+K] > max_tree.get_minimum(i+1, i+K+1):
        ans += 1
        if no_change[i] == 1:
            no_count += 1
    if i == (N-K-1) and no_change[N-K] == 1:
        no_count += 1

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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

class SegminTree:
    
    
    
    
    
    
    
    
    def __init__(self, init_val, ide_ele):
        self.ide_ele=ide_ele
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        
        for i in range(len(init_val)):
            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 segfunc(self, x, y):
        return min(x,y)
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

class SegmaxTree:
    
    
    
    
    
    
    
    
    def __init__(self, init_val, ide_ele, func):
        self.ide_ele=ide_ele
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
        self.func=func

        
        for i in range(len(init_val)):
            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 segfunc(self, x, y):
        return self.func(x,y)
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

segmin=SegminTree(p,10**9)
segmax=SegmaxTree(p,0,max)

lst=[]
for i in range(n-k+1):
    tmp1=segmin.query(i,k+i)
    tmp2=segmax.query(i,k+i)
    lst.append((tmp1,tmp2))


ans=1
for i in range(n-k):
    
    
    if lst[i][0]==p[i] and lst[i+1][1]==p[i+k]:
        continue
    else:
        ans+=1


cnt=1
cnt2=0
flag=0
for i in range(n-1):
    if p[i]<p[i+1]:
        if flag==1:
            continue
        else:
            cnt+=1
    else:
        cnt=1
        flag=0
    if cnt>=k:
        cnt2+=1
        flag=1

if cnt2>=2:
    print(ans-cnt2+1)
else:
    print(ans)

Solution (Python):
from operator import add
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e 
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func 

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    tree = SegTree(N, 10**12, min)
    tree_min = SegTree(N, 10**12, min)
    tree_max = SegTree(N, -10**12, max)
    tree_min.set_list(P)
    tree_max.set_list(P)
    tree.set_list([P[i]-P[i-1] if i else P[i] for i in range(N)])

    f = lambda l,r:tree.get(l+1, r)>=0

    ans = N-K+1
    isOrig = 0
    for i in range(N-K):
        if f(i, i+K):
            ans -= 1
            isOrig = 1
        elif tree_min.get(i, i+1+K)==P[i] and tree_max.get(i, i+1+K)==P[i+K]:
            ans -= 1
    if f(N-K, N):
        ans -= 1
        isOrig = 1
    ans += isOrig
    print(ans)


solve()

Solution (Python):
from operator import add
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e 
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func 

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


N, K = map(int, input().split())
P = list(map(int, input().split()))
tree = SegTree(N, 10**12, min)
tree_min = SegTree(N, 10**12, min)
tree_max = SegTree(N, -10**12, max)
tree_min.set_list(P)
tree_max.set_list(P)

for i in range(N):
    tree.update(i, P[i]-P[i-1] if i else P[i])

f = lambda l,r:tree.get(l+1, r)>=0

ans = N-K+1
isOrig = 0
for i in range(N-K):
    if f(i, i+K):
        ans -= 1
        isOrig = 1
    elif tree_min.get(i, i+1+K)==P[i] and tree_max.get(i, i+1+K)==P[i+K]:
        ans -= 1
if f(N-K, N):
    ans -= 1
    isOrig = 1
ans += isOrig
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 10**9+7
    

    
    N, K = map(int, input().split())
    Ps = tuple(map(int, input().split())) 
    
    
    bit=BIT(N+1)
    sc=1
    tot=0
    j=0
    cur=Ps[0]
    flag=1
    cur=Ps[0]
    it=0
    for i,p in enumerate(Ps[:K]):
        if cur>p:
            it=i
        bit.add(p+1,1)
        cur=p
    
    count=0
    if it ==0:
        count=1

    for i in range(N-K+1):
        j=i+K-1

        tot+=sc
        if i==N-K:
            break
        a=Ps[i]
        b=Ps[i+K]
        if bit.find_kth_element(1)==a+1 and bit.find_kth_element(K)<=b+1:
            sc=0
        else:
            sc=1
        bit.add(a+1,-1)
        bit.add(b+1,1)

        j=i+K
        if Ps[j-1]>Ps[j]:
            it=j
        elif j-it+1>=K:
            
            if count>0:
                sc=0
            else:
                count=1
        cur=Ps[j]
    print(tot)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
from bisect import bisect_left
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
Ps = list(map(int, input().split()))

downs = []
for i in range(N-1):
    if Ps[i+1] < Ps[i]:
        downs.append(i)

if not downs:
    print(1)
    exit()

min_wait = deque()
max_wait = deque()
for i in range(K):
    while min_wait and min_wait[-1] > Ps[i]:
        min_wait.pop()
    min_wait.append(Ps[i])
    while max_wait and max_wait[-1] < Ps[i]:
        max_wait.pop()
    max_wait.append(Ps[i])
    
change_nothing = (downs[0] >= K-1)
if change_nothing:
    ans = 0
else:
    ans = 1
    
for i in range(K, N):
    while min_wait and min_wait[-1] > Ps[i]:
        min_wait.pop()
    min_wait.append(Ps[i])
    while max_wait and max_wait[-1] < Ps[i]:
        max_wait.pop()
    max_wait.append(Ps[i])

    if min_wait[0] != Ps[i-K] or max_wait[0] != Ps[i]:
        t = bisect_left(downs, i-K+1)
        if t < len(downs):
            if downs[t] >= i:
                change_nothing = True
            else:
                ans += 1
        else:
            if downs[-1] + K < N:
                change_nothing = True
            break
    
    if min_wait[0] == Ps[i-K]:
        min_wait.popleft()
    if max_wait[0] == Ps[i-K]:
        max_wait.popleft()


if change_nothing:
    ans += 1

print(ans)

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, K, P):
    min_st = SegmentTree(P, min, INF)
    max_st = SegmentTree(P, max, -1)

    a = []
    for i in range(N-K):
        min_p = min_st.query(i, i+K+1)
        max_p = max_st.query(i, i+K+1)
        if P[i] == min_p and P[i+K] == max_p:
            a.append((i, i+K))

    j = 0
    ss = []
    for i in range(N-1):
        if P[i] < P[i+1]:
            pass
        else:
            if i - j + 1 >= K:
                ss.append((j, i+1))
            j = i + 1
    i += 1
    if i - j + 1 >= K:
        ss.append((j, i+1))

    ans = N - K + 1
    if ss:
        ans -= sum(s[1]-s[0] - K + 1 for s in ss) - 1

    ss.reverse()
    for l, r in a:
        while ss and ss[-1][1] <= l:
            ss.pop()
        if ss:
            if ss[-1][0] <= l and r < ss[-1][1]:
                pass
            else:
                ans -= 1
        else:
            ans -= 1

    return ans


def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, K, P):
    min_st = SegmentTree(P, min, INF)
    max_st = SegmentTree(P, max, -1)


    a = []
    for i in range(N-K):
        min_p = min_st.query(i, i+K+1)
        max_p = max_st.query(i, i+K+1)
        if P[i] == min_p and P[i+K] == max_p:
            a.append((i, i+K))

    j = 0
    ss = []
    for i in range(N-1):
        if P[i] < P[i+1]:
            pass
        else:
            if i - j + 1>= K:
                ss.append((j, i+1))
            j = i + 1
    i += 1
    if i - j +1 >= K:
        ss.append((j, i+1))

    ans = N - K + 1
    if ss:
        ans -= sum(s[1]-s[0] - K + 1 for s in ss) - 1

    ss.reverse()
    for l, r in a:
        while ss and ss[-1][1] <= l:
            ss.pop()
        if ss:
            if ss[-1][0] <= l and r < ss[-1][1]:
                pass
            else:
                ans -= 1
        else:
            ans -= 1


    return ans

def ref(N, K, P):
    ans = set()
    for i in range(N-K+1):
        s = tuple(P[:i] + sorted(P[i:i+K]) + P[i+K:])
        ans.add(s)
        
    return len(ans)






def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))


    
    
    
    
    
    
    
    
    
    
    
    
    



if __name__ == '__main__':
    main()

Solution (Python):
class SegmentTree:
    def __init__(self,l,init):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [init] * (self.end_leaves*2)
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i] = l[i]
            
    def stmax(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = max(self.tree[a*2:a*2+2])
            return self.tree[a]
        else:
            self.tree[a] = max(self.stmax(a*2),self.stmax(a*2+1))
            return self.tree[a]
    def stmin(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = min(self.tree[a*2:a*2+2])
            return self.tree[a]
        else:
            self.tree[a] = min(self.stmin(a*2),self.stmin(a*2+1))
            return self.tree[a]
        
    def querymax(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = 0
        tr = 0
        while y - x > 1:
            if x % 2 == 1:
                tl = max(tl,self.tree[x])
                x += 1
            if y % 2 == 0:
                tr = max(self.tree[y],tr)
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            return max(tl,tr,self.tree[x])
        else:
            return max(tl,tr,self.tree[x],self.tree[y])
    def querymin(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = float('inf')
        tr = float('inf')
        while y - x > 1:
            if x % 2 == 1:
                tl = min(tl,self.tree[x])
                x += 1
            if y % 2 == 0:
                tr = min(self.tree[y],tr)
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            return min(tl,tr,self.tree[x])
        else:
            return min(tl,tr,self.tree[x],self.tree[y])

from collections import deque

N,K = (int(x) for x in input().split())
P = list(map(int, input().split()))
d = deque(P)
st1 = SegmentTree(P,0)
st1.stmax(1)
st2 = SegmentTree(P,float('inf'))
st2.stmin(1)
combo = 0
mono_increased = False
ans = 0
comp = -1

for i in range(K):
    temp = d.popleft()
    if temp > comp:
        combo += 1
    else:
        combo = 1
    comp = temp

if combo == K:
    mono_increased = True
else:
    ans += 1
d2 = deque(P)

for i in range(1,N-K+1):
    temp = d.popleft()
    if temp > comp:
        if combo < (K-1):
            combo += 1
        elif combo == K-1:
            combo += 1
            mono_increased = True
    else:
        combo = 1
    comp = temp
    t2 = d2.popleft()
    if combo < K:
        if temp < st1.querymax(i,i+K-1):
            ans += 1
        else:
            if t2 > st2.querymin(i,i+K-1):
                ans += 1

if mono_increased == True:
    print(ans+1)
else:
    print(ans)

Solution (Python):
from operator import add
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e 
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func 

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


def solve():
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    INF = 10**12

    tree_max = SegTree(N, -INF, operator_func=max)
    tree_max.set_list(P)
    tree_min = SegTree(N, INF, operator_func=min)
    tree_min.set_list(P)
    tree_monoinc = SegTree(N, INF, operator_func=min)
    for i in range(N):
        tree_monoinc.update(i, P[i]-P[i-1] if i else 0)

    def isMonoinc(l, r):
        
        l += 1
        return tree_monoinc.get(l, r)>=0

    ans = N-K+1
    orig = 0

    for i in range(N-K+1):
        if isMonoinc(i, i+K):
            orig = 1
            ans -= 1
        elif i+K<N and tree_max.get(i, i+K+1)==P[i+K] and tree_min.get(i, i+K+1)==P[i]:
            ans -= 1

    ans += orig
    print(ans)


if __name__ == "__main__":
    solve()