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 operator import add


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, = 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)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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


class SegTree:
    
    
    
    
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        
        
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        
        
        
    
    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[2*k+1], self.seg[2*k+2])
     
    
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 
        r += self.num-2 
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return min(x,y)
def segfunc2(x,y):
    return max(x,y)

INF = 10**9
segtree = SegTree(N, P, segfunc, INF)
segtree_max = SegTree(N, P, segfunc2, 0)
from queue import Queue 

zouka = [1]
num = 1
for i in range(N-1):
    if P[i+1]>P[i]:
        num += 1
    else:
        num = 1
    zouka.append(num)


mini = INF
maxi = 0
q = Queue()
for p in P[:K]:
    mini = min(mini, p)
    maxi = max(maxi, p)
    q.put(p)

ans = 1
m = 0

if zouka[K-1]-zouka[0] == K-1:
    m += 1
    ans = 0

for i in range(1, N-K+1):
    remove = q.get()
    q.put(P[i+K-1])

    if zouka[i+K-1]-zouka[i] == K-1:
        m += 1
    elif P[i+K-1]>maxi and remove==mini:
        None
    else:
        ans += 1
    maxi = segtree_max.query(i, i+K)
    mini = segtree.query(i, i+K)


if m>=1:
    ans += 1

print(max(1,ans))

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


from collections import deque
def slide_max_index(a, K):
    
    N = len(a)
    max_idx = [0] * N 
    deq = deque() 
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() 
        while len(deq) > 0 and a[deq[-1]] < a[i] : deq.pop()   
        deq.append(i)                                          
        max_idx[i] = deq[0]                                    
    return max_idx
def slide_min_index(a, K):
    
    N = len(a)
    min_idx = [0] * N 
    deq = deque() 
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() 
        while len(deq) > 0 and a[deq[-1]] > a[i] : deq.pop()   
        deq.append(i)                                          
        min_idx[i] = deq[0]                                    
    return min_idx

min_idx=slide_min_index(p,k+1)
max_idx=slide_max_index(p,k+1)
eq=list(range(n-k+1))
for i in range(n-(k+1)+1):
  if i==min_idx[i+k] and i+k==max_idx[i+k]:
    eq[i+1]=eq[i]

pre=p[0]
a=[0]
c=0
for pi in p[1:]:
  if pre<pi:
    c+=1
  else:
    c=0
  pre=pi
  a.append(c)
eqi=-1
for i in range(n-k+1):
  if a[i+k-1]>=k-1:
    if eqi==-1:
      eqi=i
    else:
      eq[i]=eqi

print(len(set(eq)))

Solution (Python):
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree1 = [inf] * i
            tree2 = [0] * i
            break
        else:
            i *= 2
    return tree1, tree2

def update(i, x):
    j = len(tree1) // 2 + i
    tree1[j] = x
    j //= 2
    while True:
        if j == 0:
            break
        tree1[j] = min(tree1[2 * j], tree1[2 * j + 1])
        j //= 2
    j = len(tree2) // 2 + i
    tree2[j] = x
    j //= 2
    while True:
        if j == 0:
            break
        tree2[j] = max(tree2[2 * j], tree2[2 * j + 1])
        j //= 2
    return

def find(x, y):
    s = len(tree1) // 2 + x
    t = len(tree1) // 2 + y
    ans1 = inf
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans1 = min(ans1, tree1[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans1 = min(ans1, tree1[t])
            t = (t - 1) // 2
    s = len(tree2) // 2 + x
    t = len(tree2) // 2 + y
    ans2 = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans2 = max(ans2, tree2[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans2 = max(ans2, tree2[t])
            t = (t - 1) // 2
    return ans1, ans2

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = n - k + 1
s = [1] * n
for i in range(1, n):
    if p[i] > p[i - 1]:
        s[i] = s[i - 1] + 1
ans -= max(s.count(k) - 1, 0)
inf = pow(10, 7)
tree1, tree2 = make_tree(n)
for i in range(n):
    update(i, p[i])
for i in range(n - k):
    a, b = find(i, i + k)
    if a == p[i] and b == p[i + k]:
        ans -= 1
print(ans)

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

class Seg_min():
    def __init__(self,x):
        
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Solution (Python):
from collections import deque

def slide_max(A, K):
    N = len(A)
    max_idx = [0] * N
    d = deque()
    for i in range(N):
        while d and d[0] <= i-K:
            d.popleft()
        while d and A[d[-1]] < A[i]:
            d.pop()
        d.append(i)
        max_idx[i] = d[0]
    return max_idx


def slide_min(A, K):
    N = len(A)
    min_idx = [0] * N
    d = deque()
    for i in range(N):
        while d and d[0] <= i-K:
            d.popleft()
        while d and A[d[-1]] > A[i]:
            d.pop()
        d.append(i)
        min_idx[i] = d[0]
    return min_idx

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

larger_than_left = [1] * N
for i in range(1, N):
  if A[i] < A[i-1]:
    larger_than_left[i] = 0

sorted_idx = set()
num = sum(larger_than_left[1:K])
if num == K-1:
  sorted_idx.add(0)
for i in range(1, N-K+1):
  num += larger_than_left[i+K-1] - larger_than_left[i]
  if num == K-1:
    sorted_idx.add(i)

max_idx = slide_max(A, K-1)
min_idx = slide_min(A, K-1)
ans = [] if 0 in sorted_idx else [0]
for i in range(1, N-K+1):
  if i in sorted_idx:
    continue
  left = A[i-1]
  right = A[i+K-1]
  M = A[max_idx[i+K-2]]
  m = A[min_idx[i+K-2]]
  if m < left or right < M:
    ans.append(i)

print(len(ans) + (len(sorted_idx)>0))

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**6
    N,K=MI()
    P=LI()
    inf=10**6
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num




        
        def setL(self,init_val):
            
            for i in range(N):
                self.seg[i+self.num-1]=init_val[i]    
            
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        
        def update(self,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



    
    """
    長さKの尺取りぽく見るか．
    最小値が抜けて最大値が入る場合は不変．
    ただし，並び替え後も元の物と変わらない場合を何度かカウントしそう．
    事前に（元から昇順になっている長さKの列）の個数を数えておこうか．
    後からこれを引くのはダメ，事前に計算しておかないと，すでに照準になっているものを数えているのか数えていないのか不明になる．
    
    これは簡単に求まる．次が自分以上なら1をつけて，長さKの尺取りで和がKならおk．
    累積和の方が実装が楽かなあ
    """
    ans=1
    mseg=SegTree(N,inf,min)
    Mseg=SegTree(N,-1,max)
    mseg.setL(P)
    Mseg.setL(P)
    
    
    S=[0]*(N+1)
    for i in range(N-1):
        if P[i]<P[i+1]:
            S[i+1]=1
    
            
    for i in range(N):
        S[i+1]+=S[i]
    
    m=min(P[:K])
    M=max(P[:K])
    cnt=0
    if S[K]==K:
        cnt+=1
        
    for i in range(K,N):
        if m==P[i-K] and P[i]>M:
            m=mseg.query(i-K+1,i+1)
            M=P[i]
        else:
            m=mseg.query(i-K+1,i+1)
            M=Mseg.query(i-K+1,i+1)
            
            if cnt==0:
                ans+=1
            elif S[i]-S[i-K+1]!=(K-1):
                ans+=1
            if S[i]-S[i-K+1]==(K-1):
                cnt+=1
                
        

            
    print(ans)
    

main()

Solution (Python):
class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)

    def componentNum(self):
        """
        return componentNum
        """
        par_set=set()
        for p in self.parent:
            par_set.add(self.find(p))
        return len(par_set)

class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


Seg_min = SegmentTree(N,min)
Seg_max = SegmentTree(N,max,0)
for i,p in enumerate(P):
    Seg_min.set(i,p)
    Seg_max.set(i,p)
Seg_min.build()
Seg_max.build()

inc=[0]*(N+1)
for i in range(N-1):
    if P[i+1]>P[i]:
        inc[i+1]=1

for i in range(N):
    if inc[i+1]!=0:
        inc[i+1]+=inc[i]

Un=UnionFind(N-K+1)
sorted_seg_par=None

for i in range(N-K+1):
    
    if inc[i+K-1]>=K-1:
        if sorted_seg_par is None:
            sorted_seg_par=i
        else:
            Un.union(sorted_seg_par,i)
    elif i+1<N-K+1 and P[i]==Seg_min.query(i,i+K+1) and P[i+K]==Seg_max.query(i,i+K+1):
        Un.union(i,i+1)
print(Un.componentNum())

Solution (Python):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from queue import deque
from collections import defaultdict
n, k = map(int, input().split())
p = list(map(int, input().split()))

count = 0
q = deque([])
maxq = deque([])
ren = 0
prev = -1
es = defaultdict(set)
slist = []
for i,num in enumerate(p):
    if i>=k:
        m = p[q[0]]
        M = p[maxq[0]]
        if num>M and m==p[i-k]:
            count += 1
            es[i-k].add(i-k+1)
            es[i-k+1].add(i-k)

    if prev<num:
        ren += 1
        prev = num
        if ren>=k-1:
            slist.append(i-k+1)
    else:
        ren = 0
        prev = num
    
    while q and p[q[-1]]>num:
        q.pop()
    q.append(i)
    if q[0]<=i-k:
        q.popleft()
    while maxq and p[maxq[-1]]<num:
        maxq.pop()
    maxq.append(i)
    if maxq[0]<=i-k:
        maxq.popleft()
if len(slist)>=2:
    for i in range(len(slist)-1):
        es[slist[i]].add(slist[i+1])
        es[slist[i+1]].add(slist[i])
ans = 0   
seen = [False] * n
for i in range(n-k+1):
    if seen[i]:
        continue
    ans += 1
    q = [i]
    seen[i] = True
    while q:
        u = q.pop()
        for v in es[u]:
            if not seen[v]:
                q.append(v)
                seen[v] = True
print(ans)

Solution (Python):
from collections import Counter
from heapq import heappush, heappop
N,K,*P = map(int, open(0).read().split())
i = 0
ans = 1
Cnt = Counter(P[:K])
mls = []
Mls = []
for i in range(K):
  heappush(mls,P[i])
  heappush(Mls,-P[i])
for i in range(N-K):
  Cnt[P[i]] -= 1
  Cnt[P[i+K]] += 1
  if not (P[i]==mls[0] and P[i+K]>=-Mls[0]):
    ans += 1
  heappush(mls,P[i+K])
  heappush(Mls,-P[i+K])
  while Cnt[mls[0]]==0:
    heappop(mls)
  while Cnt[-Mls[0]]==0:
    heappop(Mls)
i = 0
flag = False
for j in range(1,N):
  if P[j]<P[j-1]:
    if j-i>=K:
      ans -= 1
      flag = True
    i = j
if j-i>=K-1:
  flag = True
  ans -= 1
if flag:
  ans += 1
print(ans)

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

LIS=[1 for i in range(0,N)]
s=0
t=1
while N>t:
    if P[t]>=P[t-1]:
        t+=1
        if t==N:
            ans=N-s
            while t>s:
                LIS[s]=ans
                s+=1
                ans-=1
    else:
        ans=t-s
        while t>s:
            LIS[s]=ans
            s+=1
            ans-=1
        t+=1

nochange=set([])
for i in range(0,N-K+1):
    if LIS[i]>=K:
        nochange.add(i)

n=N


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

def init(init_val):
    
    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 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 =(10**20,0)


num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
PP=[(P[i],P[i]) for i in range(0,N)]
init(PP)
ans=[]
if 0 not in nochange:
    ans.append(0)
for i in range(1,N-K+1):
    if i in nochange:
        continue
    else:
        M=query(i,i+K)[1]
        m=query(i-1,i-1+K)[0]
        if m==P[i-1] and M==P[i+K-1]:
            continue
        else:
            ans.append(i)

if nochange:
    print(len(ans)+1)
else:
    print(len(ans))

Solution (Python):
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    if i >= k - 1:
        a[i - k + 1] = p[qa[0]]
        b[i - k + 1] = p[qb[0]]
ans = l[0]
for i in range(n - k - 1):
    if (p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]) and l[i + 1]:
        ans += 1
print(ans + 1 - min(l))

Solution (Python):
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
P = list(map(int, input().split()))

INF = 2**31 - 1
N0 = 1 << (n-1).bit_length()
seg_min = [INF]*(N0 << 1)
seg_max = [0]*(N0 << 1)

def update_min(i, x):
    i += N0
    seg_min[i] = x
    while i > 1:
        y = seg_min[i ^ 1]
        if y <= x:
            break
        i >>= 1
        seg_min[i] = x
            
def query_min(l, r):
    res = INF
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = min(res, seg_min[r-1])
        if l & 1:
            res = min(res, seg_min[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_min(original):
    for i, x in enumerate(original):
        update_min(i, x)
        
def update_max(i, x):
    i += N0
    seg_max[i] = x
    while i > 1:
        y = seg_max[i ^ 1]
        if y >= x:
            break
        i >>= 1
        seg_max[i] = x
            
def query_max(l, r):
    res = 0
    l += N0
    r += N0
    while l < r:
        if r & 1:
            res = max(res, seg_max[r-1])
        if l & 1:
            res = max(res, seg_max[l])
            l += 1
        l >>= 1
        r >>= 1
 
    return res

def init_max(original):
    for i, x in enumerate(original):
        update_max(i, x)
        
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

init_min(P)
init_max(P)

uf = UnionFind(n-k+1)

for i in range(n-k):
  m = query_min(i, i+k+1)
  M = query_max(i, i+k+1)
  if m == P[i] and M == P[i+k]:
    uf.unite(i, i+1)

q = -1
s = 0
for i in range(k-1):
  if P[i] < P[i+1]:
    s += 1
if s == k-1:
  q = 0
for i in range(n-k):
  s -= int(P[i] < P[i+1])
  s += int(P[i+k-1] < P[i+k])
  if s == k-1:
    if q == -1:
      q = i+1
    else:
      uf.unite(q, i+1)
ans = uf.group_count()
print(ans)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split()))
mn = [N] * (N-K)
mx = [-1] * (N-K)
min_heap = []
max_heap = []
for i in range(K):
    heappush(min_heap, P[i])
    heappush(max_heap, -P[i])
used = set()
for i in range(N-K):
    heappush(min_heap, P[i+K])
    heappush(max_heap, -P[i+K])
    while min_heap[0] in used:
        heappop(min_heap)
    while -max_heap[0] in used:
        heappop(max_heap)
    mn[i] = min_heap[0]
    mx[i] = -max_heap[0]
    used.add(P[i])
ans = 1
for i in range(N-K):
    if P[i] != mn[i] or P[i+K] != mx[i]:
        ans += 1
inc = 1
cnt = 0
for i in range(1, N):
    if P[i-1] < P[i]:
        inc += 1
    else:
        inc = 1
    if inc == K:
        cnt += 1
ans -= max(0, cnt-1)
print(ans)

Solution (Python):
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
k -= 1
mnlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mnlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
mxlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mxlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
ans = n-k
r = set()
for i in range(1,n-k):
  if a[i-1]<mnlist[i] and mxlist[i]<a[i+k]:
    r.add(i)
flg = 0
flg2 = 0
for i in range(1,n):
  if a[i-1] < a[i]:
    flg += 1
  else:
    flg = 0
  if flg >= k:
    r.add(i-k)
    flg2 = 1
print(ans-len(r)+flg2)

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
sc=0
ans=n-k+1
INF=n+1
No=2
while No<n:
    No*=2
tree=[[0,0]]*(2*No)
for i in range(No-1,No-1+n):
    tree[i]=[l[i-No+1],l[i-No+1]]
for i in range(No-2,-1,-1):
    a,b=tree[i*2+1]
    c,d=tree[i*2+2]
    tree[i]=[max(a,c),min(b,d)]
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=[-INF,INF]
    while L<=R:
        if R&1:
            a,b=tree[R]
            c,d=s
            s=[max(a,c),min(b,d)]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            a,b=tree[L]
            c,d=s
            s=[max(a,c),min(b,d)]
        L>>=1;R>>=1
    return s
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
uf=unionfind(n)
s=set()
t=1
for i in range(n-1):
    if l[i]<l[i+1]:
        t+=1
    else:
        t=1
    if t>=k:
        s.add(i-k+2)
if len(s)>1:
    a=s.pop()
    while s:
        uf.unite(a,s.pop())
for i in range(n-k):
    b,a=query(i,i+k)
    if l[i]==a and l[i+k]==b:
        uf.unite(i,i+1)
s=set()
for i in range(n-k+1):
    s.add(uf.find(i))
print(len(s))

Solution (Python):
class BinaryIndexedTree():  
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


N, K = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))

bit = BinaryIndexedTree(N + 1)
count = 1

for i in range(K):
    bit.add(P[i], 1)

for i in range(N - K):
    mi = bit.bisect_left(1)
    ma = bit.bisect_left(K)
    if P[i] != mi or P[K + i] < ma:
        count += 1
    bit.add(P[i], -1)
    bit.add(P[K + i], 1)

inc = 1
incseq = 0

for i in range(N - 1):
    if P[i] < P[i + 1]:
        inc += 1
        if inc == K:
            incseq += 1
    else:
        inc = 1

print(count - max(0, incseq - 1))