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):
import sys
from collections import deque

input = sys.stdin.readline

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

def slide_min(P,K):
	q = deque()
	q.append(0)
	slide_minl = []
	for i in range(1,len(P)):
		while P[i]<P[q[-1]]:
			q.pop()
			if len(q)==0: break
		q.append(i)

		if i>=K-1:
			slide_minl.append(P[q[0]])
			if q[0]<=i-K+1:
				q.popleft()

	return slide_minl

def slide_max(P,K):
	q = deque()
	q.append(0)
	slide_maxl = []
	for i in range(1,len(P)):
		while P[i]>P[q[-1]]:
			q.pop()
			if len(q)==0: break
		q.append(i)

		if i>=K-1:
			slide_maxl.append(P[q[0]])
			if q[0]<=i-K+1:
				q.popleft()

	return slide_maxl

minl = slide_min(P,K)
maxl = slide_max(P,K)

if N==K:
	ans = 1
else:
	ans = 1
	for i in range(K,N):
		last = P[i]
		pre = P[i-K]
		if pre!=minl[i-K] or last!=maxl[i-K+1]:
			ans += 1
			

	count = 0
	i = 0
	while i<N-1:
		upnum = 0
		while P[i]<P[i+1]:
			upnum += 1
			i += 1
			if i==N-1: break
		if upnum>=K-1:
			count += 1
		i += 1

	ans = ans-max(count-1,0)

print(ans)

Solution (Python):
N,K=map(int,input().split())
P=list(map(int,input().split()))
from collections import deque
smin,smax=deque(),deque()
x,r,r2=0,0,0
for i,p in enumerate(P):
    while len(smin)>0 and P[smin[-1]]>p:
        smin.pop()
    smin.append(i)
    if smin[0]<=i-K:
        smin.popleft()
    while len(smax)>0 and P[smax[-1]]<p:
        smax.pop()
    smax.append(i)
    if smax[0]<=i-K:
        smax.popleft()
    if i>0 and P[i-1]<P[i]:
        x=min(x+1,K-1)
    else:
        x=0
    if i==K-1 or (i>=K and not (P[i-K]<P[smin[0]] and smax[0]==i)):
        if x!=K-1:
            r+=1
        else:
            r2=1
print(r+1 if r2 else r)

Solution (Python):
from collections import deque

def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]

n,k=MI()
a=LI()

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    for i in range(k,n):
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return b

m=slidmin(a,k)
M=[-i for i in slidmin([-i for i in a],k)]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False

for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    
    inc=1
    if c==k:
        if fl:
            inc=0
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
    ans+=inc
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7


input=sys.stdin.readline
show_flg=False


n,k=MI()
a=LI()

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    for i in range(k,n):
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return b

m=slidmin(a,k)
M=[-i for i in slidmin([-i for i in a],k)]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False

for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    
    inc=1
    if c==k:
        if fl:
            inc=0
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
    ans+=inc
print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7


input=sys.stdin.readline
show_flg=False


n,k=MI()
a=LI()
na=[-i for i in a]
qs,ql=[],[]

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    rt=[0 for _ in range(n-k+1)]
    if s==k:
        rt[0]=1
    for i in range(k,n):
        
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return rt,b

sz,m=slidmin(a,k)
sz,M=slidmin(na,k)
M=[-i for i in M]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False
show(a)
for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    inc=1
    if c==k:
        if fl:
            inc=0
            show('c==k')
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
        show('min=m,Max=M')
    show(i,inc)
    ans+=inc
print(ans)

Solution (Python):
from collections import deque
n,k=map(int,input().split())
p=list(map(int,input().split()))

minp=[0]*(n-k+1)
maxp=[0]*(n-k+1)
q1=deque([0])
q2=deque([0])
for i in range(1,k):
    while p[q1[-1]]>p[i]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i)
    q2.append(i)
for i in range(n-k+1):
    minp[i]=p[q1[0]]
    maxp[i]=p[q2[0]]
    if i==n-k:
        break
    if q1[0]==i:
        q1.popleft()
    if q2[0]==i:
        q2.popleft()
    while p[q1[-1]]>p[i+k]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i+k]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i+k)
    q2.append(i+k)

d=[0]*n
d[0]=1
for i in range(1,n):
    if p[i]>p[i-1]:
        d[i]=d[i-1]+1
    else:
        d[i]=1

ans=int(k in d)
if d[k-1]!=k:
    ans+=1
for i in range(n-k):
    if d[i+k]>=k:
        continue
    if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
        ans+=1

print(ans)

Solution (Python):
from collections import deque
n,k=map(int,input().split())
p=list(map(int,input().split()))

minp=[0]*(n-k+1)
maxp=[0]*(n-k+1)
q1=deque([0])
q2=deque([0])
for i in range(1,k):
    while p[q1[-1]]>p[i]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i)
    q2.append(i)
for i in range(n-k+1):
    minp[i]=p[q1[0]]
    maxp[i]=p[q2[0]]
    if i==n-k:
        break
    if q1[0]==i:
        q1.popleft()
    if q2[0]==i:
        q2.popleft()
    while p[q1[-1]]>p[i+k]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i+k]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i+k)
    q2.append(i+k)

d=[0]*n
d[0]=1
for i in range(1,n):
    if p[i]>p[i-1]:
        d[i]=d[i-1]+1
    else:
        d[i]=1

ans=int(k in d)
if d[k-1]!=k:
    ans+=1
for i in range(n-k):
    if d[i+k]>=k:
        continue
    if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
        ans+=1

print(ans)

Solution (Python):

import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
import random
from functools import reduce
sys.setrecursionlimit(200000)





input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()


class SparseTable():
    """SparseTable:2の冪乗ごとにテーブルを作成しておいて，min,maxなどを高速に行う。セグ木から更新を除いたもの。"""
    def __init__(self, n, func, default_value):
        self._size = n
        self.func = func
        self.default_value = default_value
        self.log2 = [0 for i in range(n + 1)]
        for i in range(2, n + 1):
            self.log2[i] = self.log2[i >> 1] + 1
        self.table = [[default_value for i in range(n)] for j in range(self.log2[n] + 1)]

    @property
    def size(self):
        return self._size

    def __getitem__(self, i):
        assert(i < self._size)
        return self.table[0][i]

    def __str__(self):
        return str(self.table[0])

    def set(self, i, val):
        assert(i < self._size)
        self.table[0][i] = (val, val)

    def build(self):
        for j in range(self.log2[self._size]):
            w = 1 << j
            for i in range(self._size - (w << 1) + 1):
                self.table[j + 1][i] = self.func(self.table[j][i], self.table[j][i + w])

    def fold(self, l, r):
        if r - l < 1:
            return self.default_value
        assert(l < self._size and r <= self._size)
        j = self.log2[r - l]
        return self.func(self.table[j][l], self.table[j][r - (1 << j)])

    def max(self, l, r):
        return self.fold(l, r)[0]

    def min(self, l, r):
        return self.fold(l, r)[1]


class UnionFind():
    '''
    UnionFind木

    Parameters
    --------
        n (int): UnionFind木のサイズ

    Methods
    --------
        unite(x: int, y: int) -> None
            ノード x とノード y を結合する
        same(x: int, y: int) -> bool
            ノード x とノード y が同じ集合に属するか判定する
        size(x: int) -> int
            ノード x を含む集合の要素数を返す

    '''

    def __init__(self, n):
        self._data = [-1] * n

    def unite(self, x: int, y: int) -> bool:
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False  
        elif self._data[x] > self._data[y]:
            x, y = y, x  
        self._data[x] += self._data[y]
        self._data[y] = x
        return True

    def root(self, x: int) -> int:
        '''ノード x の親を返す'''
        while self._data[x] >= 0:
            x = self._data[x]
        return x

    def same(self, x: int, y: int) -> bool:
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        '''x を含むグループのノード数を返す'''
        return -self._data[self.root(x)]



def generate_testcase():
    N = 200000
    K = 10000
    with open('in_1.txt', 'w') as f:
        print(N, K, file=f)
        a = [i for i in range(N)]
        random.shuffle(a)
        print(*a, file=f)

def bruteforce(N, K, P):
    s = set()
    for i in range(N - K + 1):
        d = deepcopy(P)
        d[i:i + K] = sorted(d[i:i + K])
        s.add(''.join(list(map(str, d))))
    return len(s)

def main():
    N, K = mi()
    P = lmi()
    
    def func(x: tuple, y: tuple):
        return (max(x[0], y[0]), min(x[1], y[1]))
    spt = SparseTable(N, func, (int(-1e9), int(1e9)))
    for i, val in enumerate(P):
        spt.set(i, val)
    spt.build()
    uf = UnionFind(N - K + 1)
    
    right = 1  
    left = 0
    ans = 0
    s = []
    while left < N - K + 1:
        
        while (right < N and (right <= left or P[right - 1] < P[right])):
            right += 1
        if right - left >= K:
            s.append(left)
        if left == right:
            right += 1
        left += 1
    if len(s) >= 2:
        for i in range(1, len(s)):
            uf.unite(s[0], s[i])
    for i in range(N - K):
        if P[i] == spt.min(i, i + K + 1) and spt.max(i, i + K + 1) == P[i + K]:
            uf.unite(i, i + 1)
    for i in range(N - K + 1):
        if uf.root(i) == i:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    
    
    
    main()

Solution (Python):
from collections import deque

n,k=map(int,input().split())
p=list(map(int,input().split()))+[1000000]

p1=[0]*(n)
pmin=[0]*(n+1)
pmax=[0]*(n+1)

cnt=0

for i in range(n-1):
  if p[i]<p[i+1]:
    cnt+=1
  else:
    cnt=0
  p1[i+1]=cnt

d=deque()
d.append(0)

for i in range(1,k+1):
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
pmin[k]=p[d[0]]

for i in range(k+1,n):
  if d[0]==i-(k+1):
    d.popleft()
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
  pmin[i]=p[d[0]]


dd=deque()
dd.append(0)

for i in range(1,k+1):
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
pmax[k]=p[dd[0]]

for i in range(k+1,n):
  if dd[0]==i-(k+1):
    dd.popleft()
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
  pmax[i]=p[dd[0]]

ans=n-k+1
f=1
ff=[0]*n
for i in range(n):
  if p1[i]>=k-1:
    ff[i]=1
    if f==0:
      ans-=1
    else:
      f=0

for i in range(n-k):
  if p[i]==pmin[i+k] and p[i+k]==pmax[i+k] and ff[i+k]==0:
    ans-=1

print(ans)

Solution (Python):
import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

_min = [(x,i) for i,x in enumerate(p[:k])]
_max = [(-x,i) for i,x in enumerate(p[:k])]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, (p[i+k], i+k))
    heapq.heappush(_max, (-p[i+k], i+k))
    
    while _min[0][1] < i:
        heapq.heappop(_min)
    while _max[0][1] < i:
        heapq.heappop(_max)
    
    if (_min[0][0]==p[i] and -_max[0][0]==p[i+k]):
        ans -= 1
        decrease = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

print(ans)

Solution (Python):
import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

c = [False] * n

_min = p[:k].copy()
_max = [-x for x in p[:k]]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, p[i+k])
    heapq.heappush(_max, -p[i+k])
    
    while c[_min[0]]:
        heapq.heappop(_min)
    while c[-_max[0]]:
        heapq.heappop(_max)
    
    if (_min[0]==p[i] and -_max[0]==p[i+k]):
        ans -= 1
        decrease = True
    
    c[p[i]] = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

print(ans)

Solution (Python):
from collections import deque

class SlideMin:
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value=0):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

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

maxQ = SlideMin(K)
minQ = SlideMin(K)

for i in range(K):
    maxQ.update(i, -P[i])
    minQ.update(i, P[i])

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    maxQ.update(right, -P[right])

    if left == minQ.top()[0] and right == maxQ.top()[0]:
        pass
    else:
        if seq < K:
            ans += 1
        else:
            if not hasSame:
                hasSame = True
                ans += 1

    minQ.update(right, P[right])

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def ff(n,k,p):
    s = set()
    for i in range(n-k+1):
        t = tuple(p[:i] + sorted(p[i:i+k]) + p[i+k:])
        s.add(t)

    return len(s)

def main():
    n,k = LI()
    p = LI()
    qc = [None] * n
    for i in range(n-1):
        if p[i] > p[i+1]:
            qc[i+1] = True

    ec = -1
    iq = []
    aq = []
    for i in range(k):
        if qc[i]:
            ec = i
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])


    r = 0
    if ec > 0:
        r += 1
    s = set()
    for i in range(k,n):
        if qc[i]:
            ec = i
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            if ec > i - k + 1:
                r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i] > p[i-1]:
            c += 1
            if c >= k:
                rr = 1
                break
        else:
            c = 1

    return r + rr


print(main())

Solution (Python):




import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
p = LI()
ans = 0
que = deque()
que.append(0)
minlst = []
for i in range(1,n):
    if p[que[-1]] < p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] < p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k:
        minlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()
minlst.append(p[que[0]])
que = deque()
que.append(0)
maxlst = []
for i in range(1,n):
    if p[que[-1]] > p[i]:
        que.append(i)
    else:
        while que:
            if p[que[-1]] > p[i]:
                que.append(i)
                break
            else:
                que.pop()
        else:
            que.append(i)
    if i >= k-1:
        maxlst.append(p[que[0]])
        if que[0] == i - k:
            que.popleft()

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]
def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

lst = []
cnt = 1
tmp = p[0]
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        if cnt >= k:
            lst.append(i-k)
        cnt = 1
    tmp = p[i]
if cnt >= k:
    lst.append(i-cnt+1)
par = [i for i in range(n)]
rank = [0]*n
if len(lst) > 1:
    for i in lst:
        for j in lst[::-1]:
            union(i,j)
for i in range(n-k):
    if p[i] == minlst[i] and p[i+k] == maxlst[i+1]:
        union(i,i+1)
s = set()
for i in range(n-k+1):
    s.add(root(i))
print(len(s))

Solution (Python):
from collections import deque

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

maxQ = deque([])
minQ = deque([])

for i in range(K):
    while maxQ:
        if P[maxQ[-1]] <= P[i]:
            maxQ.pop()
        else:
            break
    maxQ.append(i)
    if maxQ[0] == i - K:
        maxQ.popleft()

    while minQ:
        if P[minQ[-1]] >= P[i]:
            minQ.pop()
        else:
            break
    minQ.append(i)
    if minQ[0] == i - K:
        minQ.popleft()

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    while maxQ:
        if P[maxQ[-1]] <= P[right]:
            maxQ.pop()
        else:
            break
    maxQ.append(right)
    if maxQ[0] == right - K:
        maxQ.popleft()

    if left == minQ[0] and right == maxQ[0]:
        pass
    else:
        if seq < K:
            ans += 1
        else:
            if not hasSame:
                hasSame = True
                ans += 1

    while minQ:
        if P[minQ[-1]] >= P[right]:
            minQ.pop()
        else:
            break
    minQ.append(right)
    if minQ[0] == right - K:
        minQ.popleft()

print(ans)

Solution (Python):
from collections import deque
import itertools




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

deq = deque()
min_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] >= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    min_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()


deq = deque()
max_val = [0] * (N - K + 1)
for i in range(N):
  while deq and p[deq[-1]] <= p[i]:
    deq.pop()
  deq.append(i)

  if i - K + 1 >= 0:
    max_val[i - K + 1] = p[deq[0]]
    if deq[0] == i - K + 1:
      deq.popleft()


incr = [1 if x<y else 0 for x,y in zip(p, p[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

cnt = 0
preL = -1
prerange_min = -2
sortMatchCnt = 0
for i in range(N - K + 1):
  range_min = min_val[i]
  range_max = max_val[i]
  l = p[i]
  r = p[i + K - 1]

  sortMatchFlg = False
  if is_stable[i]:
    sortMatchCnt += 1
    sortMatchFlg = True

  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  
  prerange_min = range_min
  
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Solution (Python):
n, k = list(map(int, input().split()))
xs = list(map(int, input().split()))
from collections import deque
def slide_max(k, l):
    rs, rrs = [], set()
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x < l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

def slide_min(k, l):
    rs = []
    rrs = set()
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x > l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        if len(dq) == k:
            rrs.add(i+1-k)
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs, rrs

maxs, (mins, ns) = slide_max(k, xs), slide_min(k, xs)
r = 1
for i, (s, x) in enumerate(zip(xs, xs[k:])):
    if (x != maxs[i+1] or s != mins[i]) and (i+1 not in ns): 
        r+=1
if (0 not in ns) and (len(ns) > 0):
    r += 1
print(r)

Solution (Python):
from collections import deque
def slidemax(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] <= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

def slidemin(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] >= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

a = 0
l = -1
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]: a = i
    if i >= K-1 and a <= i - K + 1:
        if i - l > 1: cnt += 1
        l = i

MA = slidemax(A, K)
MI = slidemin(A, K)
ans = 1 - max(cnt-1, 0)
l = -1
for i in range(K, N):
    if MI[i-K] != A[i-K] or MA[i-K+1] != A[i]:
        ans += 1

print(ans)

Solution (Python):
n, k = list(map(int, input().split()))
xs = list(map(int, input().split()))

from collections import deque
def slide_max(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x < l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

def slide_min(k, l):
    rs = []
    dq = deque()
    for i, x in enumerate(l):
        while True:
            if not len(dq):
                dq.append(i)
                break
            lxi = dq[-1]
            if x > l[lxi]:
                dq.append(i)
                break
            dq.pop()
        if i+1 < k:
            continue
        sxi = dq[0]
        rs.append(l[sxi])
        if sxi == (i + 1 - k):
            dq.popleft()
    return rs

maxs, mins = slide_max(k, xs), slide_min(k, xs)
aa, bb = xs[:k], xs[k:]

b, nb, bx = aa[0], aa[1], aa[-1]
ba = None
c = 1
for a in aa:
    if ba == None:
        ba = a
        continue
    if a > ba:
        c += 1
    else:
        c = 1
    ba = a

rok = False
if c == k:
    rok = True

r = 1
bs = xs[0]
for i, (s, x) in enumerate(zip(xs[1:], bb)):

    if x > bx:
        c = min(c+1, k)
    else:
        c = 1
    bx = x

    if c == k:
        if not rok:
            r += 1
        rok = True
        continue

    if x != maxs[i+1]: 
        r+=1
    elif bs != mins[i]:
        r+=1
    bs = s

print(r)

Solution (Python):
from collections import deque
def slidemax(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] <= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

def slidemin(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] >= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

a = 0
l = -1
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]: a = i
    if i >= K-1 and a <= i - K + 1:
        if i - l > 1: cnt += 1
        l = i

MA = slidemax(A, K)
MI = slidemin(A, K)
ans = 1 - max(cnt-1, 0)
l = -1
for i in range(K, N):
    if MI[i-K] != A[i-K] or MA[i-K+1] != A[i]:
        ans += 1

print(ans)