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):
from heapq import heappush, heappop
N, K , *P = map(int, open(0).read().split())
mhq = []
Mhq = []
for c in P[:K]:
  heappush(mhq,c)
  heappush(Mhq,-c)

ans = 1
log = set()
for i,c in enumerate(P[K:]):
  while mhq[0] in log:
    heappop(mhq)
  while -Mhq[0] in log:
    heappop(Mhq)
  d = P[i]
  m = mhq[0]
  M = -Mhq[0]
  log.add(d)
  heappush(mhq,c)
  heappush(Mhq,-c)
  if not (m==d and M<c):
    ans += 1
p = P[0]
m = 1
x = 0
for c in P[1:]:
  if p<c:
    m += 1
  else:
    if m>=K:
      x += 1
    m = 1
  p = c
if m>=K:
  x += 1
if x!=0:
  ans -= x-1
print(ans)

Solution (Python):
class SegmentTree:
    def __init__(self, N, f, e=None):
        self.N = 1<<(N-1).bit_length()
        self.seg = [e] * (self.N*2)
        self.e = e
        self.f = f

    def build(self, A):
        for i,a in enumerate(A):
            self.seg[i+self.N] = a
        for i in range(self.N-1,0,-1):
            self.seg[i] = self.f(self.seg[i<<1], self.seg[i<<1|1])

    def update(self, i, x): 
        i += self.N
        self.seg[i] = x
        while i > 1:
            self.seg[i>>1] = self.f(self.seg[i], self.seg[i^1])
            i >>= 1

    def query(self, a, b): 
        L = R = self.e
        a += self.N
        b += self.N
        while a < b:
            if a&1:
                L = self.f(L, self.seg[a])
                a += 1
            if b&1:
                b -= 1
                R = self.f(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.f(L, R)

from collections import Counter
def main():
    N,K,*P=map(int, open(0).read().split())
    Mseg=SegmentTree(N, max, 0)
    mseg=SegmentTree(N, min, float("inf"))
    Mseg.build(P)
    mseg.build(P)
    D=Counter(P[:K])
    ans=1
    als=1
    for i in range(1,K):
        als=als+1 if P[i]>P[i-1] else 1
    iss=als==K
    for i in range(N-K):
        als=als+1 if P[i+K]>P[i+K-1] else 1
        mp=mseg.query(i, i+K)
        Mp=Mseg.query(i+1,i+K+1)
        if not (mp==P[i] and Mp==P[i+K]) and not (iss and als==K):
            ans+=1
        iss|=als==K
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

N, K = lr()
P = lr()
mi = slide_min(P, K)
ma = slide_min([-x for x in P], K)
new_pattern = [not (mi == i and ma == i+K) for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]

increase = [0] + list(accumulate(x<y for x, y in zip(P, P[1:])))

stable_increase = [y-x == K-1  for x, y in zip(increase, increase[K-1:])]
answer = 1 + sum([x for x, y in zip(new_pattern, stable_increase[1:]) if not y])
if not stable_increase[0] and any(stable_increase):
    answer += 1
print(answer)

Solution (Python):
from collections import deque


def slide_min(L: int, li: list):
	deq = deque()
	ret = []
	for i, x in enumerate(li):
		while deq and deq[-1][1] > x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]


def slide_max(L: int, li: list):
	deq = deque()
	ret = []
	for i, x in enumerate(li):
		while deq and deq[-1][1] < x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]


n, k, *a = map(int, open(0).read().split())
m, M = slide_min(k - 1, a), slide_max(k - 1, a)
ans = 1
for i in range(n - k):
	if not (a[i] < m[i + 1] and M[i + 1] < a[i + k]):
		ans += 1
cnt = 1
subt = 0
for x, y in zip(a, a[1:]):
	if x < y:
		cnt += 1
	else:
		cnt = 1
	if cnt == k:
		subt += 1
if subt:
	ans -= subt - 1

print(ans)

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            

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

        def unite(self, x, y):
            
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

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

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

        def is_root(self, x):
            
            return self.parent[x] < 0

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

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

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

        def all_group_members(self):
            
            return {r: self.members(r) for r in self.roots()}
    class segment_():
        def __init__(self, A, n, segfunc,ide_ele):
            
            self.ide_ele = ide_ele
            
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            
            for i in range(n):
                self.seg[i + self.num] = A[i]
                
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, K = LI()
    P = LI()
    Seg_min = segment_(P, N, lambda a, b: min(a,b),inf)
    Seg_max = segment_(P, N, lambda a, b: max(a, b),-inf)
    DL = defaultdict(bool)
    DR = defaultdict(bool)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            DL[i] = True
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            DR[i+K-1] = True
    
    uf = UnionFind(N)
    bigger = [False]*N
    skip = []
    for i in range(N-1):
        if P[i+1]>P[i]:
            bigger[i] = True
    cur = sum(bigger[:K-1])
    if cur == K - 1:
        skip.append(0)
    for i in range(N-K):
        if bigger[i+K-1]:
            cur += 1
        if bigger[i]:
            cur -= 1
        if cur==K-1:
            skip.append(i+1)
    
    
    for i in range(len(skip)-1):
        uf.unite(skip[i],skip[i+1])

    for i in range(N-K):
        if DL[i] and DR[i+K]:
            uf.unite(i,i+1)
    ans = set()
    for i in range(N-K+1):
        cur = uf.find(i)
        
        ans.add(cur)
    print(len(ans))
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""
9 4
8 0 1 2 3 4 5 6 7 

9 2
6 7 8 3 4 5 0 1 2

13 4
9 10 11 12 2 1 0 6 7 8 3 4 5
"""

Solution (Python):
from collections import deque


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

smin = deque()
smax = deque()
x = 0
r = 0
r2 = 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 heapq import heappush, heappop

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

h_max = []
h_min = []
for i in range(K):
  heappush(h_min,  A[i])
  heappush(h_max, -A[i])

check = [0] * (N + 1)
tmp = [0] * N
tmp[0] = 1
for i in range(N - K):
  
  a_min =  heappop(h_min)
  a_max = -heappop(h_max)
  while check[a_min]:
    a_min =  heappop(h_min)
  while check[a_max]:
    a_max = -heappop(h_max)
  if A[i] == a_min and A[i + K] > a_max:
    tmp[i + 1] -= 1
  check[A[i]] = 1
  heappush(h_min,  a_min)
  heappush(h_max, -a_max)  
  heappush(h_min,  A[i + K])
  heappush(h_max, -A[i + K])  
  tmp[i + 1] += 1

B = [0]
for i in range(1, N):
  if A[i] > A[i - 1]:
    B.append(1)
  else:
    B.append(0)

sum_B = sum(B[1: K])
flag = 0
for i in range(N - K + 1):
  if sum_B == K - 1:
    if tmp[i]:
      flag = 1
      tmp[i] = 0
  if i == N - K:
    break
  sum_B = sum_B - B[i + 1] + B[i + K]

print(sum(tmp) + flag)

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

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

minst, maxst = SegmentTree(n), SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
minst.build(p)
maxst.build(p)

ans = n - k + 1
for i in range(n-k):
    j = i + k
    if minst.query(i, j+1) == p[i] and maxst.query(i, j+1) == p[j]:
        ans -= 1

srted = [1] * n
cnt = 0
for i in range(n):
    if p[i] > p[i-1]: srted[i] = srted[i-1] + 1
    if srted[i] == k: cnt += 1

if cnt > 1: ans -= cnt - 1

print(ans)

Solution (Python):
from collections import deque
from bisect import bisect_right
N,K = map(int,input().split())
P = list(map(int,input().split()))
Lmax = []
Lmin = []
if P[1]>P[0]:
    flag = 1
else:
    flag = -1
for i in range(2,N):
    if P[i]>P[i-1]:
        if flag==1:continue
        else:
            Lmin.append([i-1,P[i-1]])
            flag = 1
    else:
        if flag==1:
            Lmax.append([i-1,P[i-1]])
            flag = -1
        else:continue
cnt = 0
flagMono = 0
indmin = bisect_right(Lmin,[K-1,P[K-1]])
Smax = deque([0])
Smin = deque([0])
for i in range(1,K):
    while Smax:
        if P[Smax[-1]]<P[i]:
            Smax.pop()
        else:break
    Smax.append(i)
    while Smin:
        if P[Smin[-1]]>P[i]:
            Smin.pop()
        else:break
    Smin.append(i)    
if P[0]==P[Smin[0]] and P[K-1]==P[Smax[0]] and (len(Lmin)==0 or indmin==0 or Lmin[indmin-1][0]==0):
    flagMono=1
    cnt += 1
elif P[0]==P[Smin[0]] and K<N and P[K]>P[Smax[0]]:
    pass
else:
    cnt += 1
for i in range(1,N-K+1):
    if Smax[0]==i-1:
        Smax.popleft()
    while Smax:
        if P[Smax[-1]]<P[i+K-1]:
            Smax.pop()
        else:break
    Smax.append(i+K-1)
    if Smin[0]==i-1:
        Smin.popleft()
    while Smin:
        if P[Smin[-1]]>P[i+K-1]:
            Smin.pop()
        else:break
    Smin.append(i+K-1)
    indmin = bisect_right(Lmin,[i+K-1,P[i+K-1]])
    if P[i]==P[Smin[0]] and P[i+K-1]==P[Smax[0]] and (len(Lmin)==0 or indmin==0 or Lmin[indmin-1][0]<=i):
        if flagMono==0:
            flagMono = 1
            cnt += 1
        else:
            pass
    elif P[i]==P[Smin[0]] and i+K<N and P[i+K]>P[Smax[0]]:
        continue
    else:
        cnt += 1
print(cnt)

Solution (Python):
N,K = map(int,input().split())
P = list(map(int,input().split()))
if K==N:
    print(1)
    exit()

cum_asc = [0]
for p,q in zip(P,P[1:]):
    cum_asc.append(cum_asc[-1] + int(p<q))
all_asc = []
for i in range(N-K+1):
    all_asc.append(cum_asc[i+K-1] - cum_asc[i] == K-1)

from collections import deque
sldmin = []
sldmax = []
qmin = deque()
qmax = deque()
for i,p in enumerate(P):
    while qmin and qmin[-1] > p:
        qmin.pop()
    qmin.append(p)
    if i-K-1 >= 0 and P[i-K-1] == qmin[0]:
        qmin.popleft()
    while qmax and qmax[-1] < p:
        qmax.pop()
    qmax.append(p)
    if i-K-1 >= 0 and P[i-K-1] == qmax[0]:
        qmax.popleft()
    if i >= K:
        sldmin.append(qmin[0])
        sldmax.append(qmax[0])

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def components(self):
        return len(self.parent) - self.count

uf = UnionFind(N-K+2)
for i,(l,r,mn,mx) in enumerate(zip(P,P[K:],sldmin,sldmax)):
    if l==mn and r==mx:
        uf.unite(i,i+1)
if all(f == False for f in all_asc):
    print(uf.components() - 1)
    exit()

def_i = N-K+1 
for i,f in enumerate(all_asc):
    if f:
        uf.unite(i, def_i)
print(uf.components())

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def init(init_val,n):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def segfunc(x,y):
    return max([x,y])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

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


ide_ele = 0


num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

def init2(init_val,n):
    
    for i in range(n):
        seg2[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg2[i]=segfunc2(seg2[2*i+1],seg2[2*i+2])

def segfunc2(x,y):
    return min([x,y])

def update2(k,x):
    k += num-1
    seg2[k] = x
    while k:
        k = (k-1)//2
        seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

def query2(p,q):
    if q<=p:
        return ide_ele2
    p += num-1
    q += num-2
    res=ide_ele2
    while q-p>1:
        if p&1 == 0:
            res = segfunc2(res,seg2[p])
        if q&1 == 1:
            res = segfunc2(res,seg2[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc2(res,seg2[p])
    else:
        res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
    return res


ide_ele2 = 10**9


num =2**(N-1).bit_length()
seg2=[ide_ele2]*2*num

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
tmp = sum(l[0:K-1])
for i in range(N-K+1):
    if tmp==0:
        l2[i]=1
    if i != N-K:
        tmp += (l[i+K-1]-l[i])
init(P,N)
init2(P,N)
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif  (P[i-1] < query2(i,i+K-1)) and (P[i+K-1] > query(i,i+K-1)) and (i!=0):
        continue
    else:
        count += 1
print(count)

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        
        if A:
            
            for i in range(n):
                self.tree[n2+i] = A[i]
            
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

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


stmin = SegTree(N, min, INF, A)
stmax = SegTree(N, max, -INF, A)
total = N - K + 1
dup = 0
for i in range(N-K):
    mn = stmin.query(i, i+K+1)
    mx = stmax.query(i, i+K+1)
    if mn == A[i] and mx == A[i+K]:
        dup += 1


B = [0] * N
for i in range(N-1):
    
    if A[i] < A[i+1]:
        B[i+1] = 1
B = list(accumulate(B))

prev = INF
for i in range(N-K+1):
    
    if B[i+K-1] - B[i] == K - 1:
        
        if prev + K - 1 < i:
            dup += 1
        prev = i

print(total - dup)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class SparseTable(object):
    def __init__(self,A):
        n=len(A)
        logn=max(0,(n-1).bit_length())
        maxtable=[[0]*n for _ in range(logn)]
        maxtable[0]=A[:]
        mintable=[[0]*n for _ in range(logn)]
        mintable[0]=A[:]
        from itertools import product
        for i,k in product(range(1,logn),range(n)):
            if(k+(1<<(i-1))>=n):
                maxtable[i][k]=maxtable[i-1][k]
                mintable[i][k]=mintable[i-1][k]
            else:
                maxtable[i][k]=max(maxtable[i-1][k],maxtable[i-1][k+(1<<(i-1))])
                mintable[i][k]=min(mintable[i-1][k],mintable[i-1][k+(1<<(i-1))])
        self.__n=n
        self.__maxtable=maxtable
        self.__mintable=mintable

    def max(self,l,r):
        n=self.__n
        assert 0<=l<r<=n
        i=max(0,(r-l-1).bit_length()-1)
        maxtable=self.__maxtable
        return max(maxtable[i][l],maxtable[i][r-(1<<i)])

    def min(self,l,r):
        n=self.__n
        assert 0<=l<r<=n
        i=max(0,(r-l-1).bit_length()-1)
        mintable=self.__mintable
        return min(mintable[i][l],mintable[i][r-(1<<i)])

def resolve():
    n,k=map(int,input().split())
    P=list(map(int,input().split()))
    table=SparseTable(P)
    ans=n-k+1
    for i in range(n-k):
        m=table.min(i,i+k)
        M=table.max(i+1,i+1+k)
        if(m==P[i] and M==P[i+k]):
            ans-=1

    cnt=0
    num=0
    P.append(-1) 
    for i in range(n):
        if(P[i+1]>P[i]):
            cnt+=1
        else:
            num+=(cnt>=k-1)
            cnt=0
    ans-=max(num-1,0)
    print(ans)
resolve()

Solution (Python):
INF = 10**30

class Rmax():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [-INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
		return

	
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = -INF
		while L<R:
			if R & 1:
				R -= 1
				s = max(s, self.node[R-1])
			if L & 1:
				s = max(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

class Rmin():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, k = map(int, input().split())
p = list(map(int, input().split()))
ma, mi = Rmax(n), Rmin(n)
for i in range(n):
	ma.Update(i, p[i])
	mi.Update(i, p[i])
ans = n-k+1
same = set()
tmp = 0
for i in range(1, n):
	if p[i-1] < p[i]:
		tmp += 1
	else:
		tmp = 0
	if tmp >= k-1:
		same.add(i-k+1)
ans -= max(0, len(same)-1)
for i in range(k, n):
	if p[i-k] < mi.Get(i-k+1, i) and ma.Get(i-k+1, i) < p[i]:
		if not i-k in same and not i-k+1 in same:
			ans -= 1
print(ans)

Solution (Python):
import heapq

N,K = map(int, input().split())
P = [int(p) for p in input().split()]

h = []
H = []
for i in range(K):
    heapq.heappush(h, (P[i], i))
    heapq.heappush(H, (-P[i], i))
    
ans = 1
for i in range(N-K):
    while h[0][1] < i:
        heapq.heappop(h)
    while H[0][1] < i:
        heapq.heappop(H)
    heapq.heappush(h, (P[i+K], i+K))
    heapq.heappush(H, (-P[i+K], i+K))
    if h[0][0] == P[i] and -H[0][0] == P[i+K]:
        continue
    ans += 1
    
f = 0
cnt = 1
for i in range(N-1):
    if P[i] < P[i+1]:
        cnt += 1
    else:
        if cnt >= K and f == 1:
            ans -= 1
        elif cnt >= K and f == 0:
            f = 1
        cnt = 1
        
if cnt >= K and f == 1:
    ans -= 1
    
print(ans)

Solution (Python):

class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    
    
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    
    
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    
    
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()
    
import sys
input = sys.stdin.readline

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

bit = BITbisect(N)

for i in range(K):
    bit.insert(A[i]+1)

ans = 1
for i in range(K, N):
    if A[i-K]+1 != bit.search(0) or A[i]+1 <= bit.search(K-1):
        ans += 1
    bit.delete(A[i-K]+1)
    bit.insert(A[i]+1)

c = 1
p = 0
for i in range(N-1):
    if A[i] < A[i+1]:
        c += 1
    else:
        if c >= K:
            p += 1
        c = 1
if c >= K:
    p += 1

ans -= max(p-1, 0)

print(ans)

Solution (Python):
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)

Solution (Python):
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
n,k,*p=map(int,open(0).read().split())
c=[0]
for a,b in zip(p,p[1:]):c+=c[-1]+(a<b),
*c,f=[b-a==k-1for a,b in zip(c,c[k-1:])]
x=not f
s_min=SWAG(10**18,min,p[:k-1])
s_max=SWAG(0,max,p[1:k])
for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    s_min.append(p[i+k-1])
    s_max.append(b)
    if not c and(a!=s_min.fold_all()or b!=s_max.fold_all()):x+=1
    s_min.popleft()
    s_max.popleft()
print(x+f)