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):
def main():
  def update(k,x):
    k+=N0-1
    data_min[k]=data_max[k]=x
    while k>=0:
      k=(k-1)//2
      a,b=data_min[2*k+1],data_min[2*k+2]
      data_min[k]=a if a<b else b
      a,b=data_max[2*k+1],data_max[2*k+2]
      data_max[k]=a if a>b else b
  def query_min(l,r):
    L,R=l+N0,r+N0
    s=INF
    while L<R:
      if R&1:
        R-=1
        t=data_min[R-1]
        if t<s:s=t
      if L&1:
        t=data_min[L-1]
        if t<s:s=t
        L+=1
      L//=2
      R//=2
    return s
  def query_max(l,r):
    L,R=l+N0,r+N0
    s=0
    while L<R:
      if R&1:
        R-=1
        t=data_max[R-1]
        if t>s:s=t
      if L&1:
        t=data_max[L-1]
        if t>s:s=t
        L+=1
      L//=2
      R//=2
    return s
  n,k,*p=map(int,open(0).read().split())
  N0=2**(n-1).bit_length()
  INF=10**18
  data_min=[INF]*2*N0
  data_max=[0]*2*N0
  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
  for i,q in enumerate(p):update(i,q)
  for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    if not c and(a!=query_min(i,i+k)or b!=query_max(i+1,i+k+1)):x+=1
  print(x+f)
main()

Solution (Python):
def main():
  def update(k,x):
    k+=N0-1
    data_min[k]=data_max[k]=x
    while k>=0:
      k=(k-1)//2
      a,b=data_min[2*k+1],data_min[2*k+2]
      data_min[k]=a if a<b else b
      a,b=data_max[2*k+1],data_max[2*k+2]
      data_max[k]=a if a>b else b
  def query_min(l,r):
    L,R=l+N0,r+N0
    s=INF
    while L<R:
      if R&1:
        R-=1
        t=data_min[R-1]
        if t<s:s=t
      if L&1:
        t=data_min[L-1]
        if t<s:s=t
        L+=1
      L//=2
      R//=2
    return s
  def query_max(l,r):
    L,R=l+N0,r+N0
    s=0
    while L<R:
      if R&1:
        R-=1
        t=data_max[R-1]
        if t>s:s=t
      if L&1:
        t=data_max[L-1]
        if t>s:s=t
        L+=1
      L//=2
      R//=2
    return s
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
      if table[x]>table[y]:x,y=y,x
      table[x]+=table[y]
      table[y]=x
  def same(x,y):return root(x)==root(y)
  def size(x):return-table[root(x)]
  n,k,*p=map(int,open(0).read().split())
  N0=2**(n-1).bit_length()
  INF=10**18
  data_min=[INF]*2*N0
  data_max=[0]*2*N0
  table=[-1]*n
  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
  for i,q in enumerate(p):update(i,q)
  for i,(a,b,c)in enumerate(zip(p,p[k:],c)):
    f|=c
    if not c and(a!=query_min(i,i+k)or b!=query_max(i+1,i+k+1)):x+=1
  print(x+f)
main()

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

def init_max(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update_max(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query_max(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 = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res

def init_min(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2]) 
    
def update_min(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1],seg[k*2+2])
    
def query_min(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 = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res



ide_ele = -1


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

init_max(p)

a = [-1]*(n-k+1)
for i in range(n-k+1):
    a[i] = query_max(i,i+k)


ide_ele = n


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

init_min(p)

b = [-1]*(n-k+1)
for i in range(n-k+1):
    b[i] = query_min(i,i+k)

c = [1]*n
d = [True]*n
for i in range(n-2,-1,-1):
    if p[i] < p[i+1]:
        c[i] = c[i+1]+1
        if c[i] >= k:
            d[i] = False



res = 0
res2 = 0


for i in range(n-k):
    if not d[i]:
        res2 = 1
        continue
    if b[i] == p[i] and a[i+1] == p[i+k]:
        continue
    res += 1
if d[n-k]:
    res += 1

if n==k:
    print(1)
else:
    print(res+res2)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class SegmentTree:
    def __init__(self, init_val, ide_ele, op):
        n = len(init_val)
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        self.op = op
        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.op(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.op(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.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res


n, k = LI()
L = LI()
min_ST = SegmentTree(L, INF, min)
max_ST = SegmentTree(L, -INF, max)
cnt = 1
for i in range(n - k):
    if min_ST.query(i, i + k) == L[i] and max_ST.query(i + 1, i + k + 1) == L[i + k]:
        continue
    else:
        cnt += 1

ret = -INF
increasing_block_num = 0
max_len = 0
for j in range(n):
    if L[j] >= ret:
        max_len += 1

    else:
        if max_len >= k:
            increasing_block_num += 1
        max_len = 1
    ret = L[j]

if max_len >= k:
    increasing_block_num += 1

if increasing_block_num:
    print(cnt - (increasing_block_num - 1))
else:
    print(cnt)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.n + 1)
        self.num = 0
    def 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.n:
            self.data[i] += x
            i += i & -i
        self.num+=1
    def search(self, value):
        if value<1:
            return 0
        if value >self.num:
            return self.N+1
        x,sx = 0,0
        step = self.n
        while step:
            y = x+step
            sy = sx+self.data[y]
            if sy < value:
                x,sx = y,sy
            step >>= 1
        return x+1
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
from collections import deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
B = BIT(N)
U = UnionFind(N)
ans = N-K+1
for i in range(K):
    B.add(P[i]+1, 1)
for i in range(1, N-K+1):
    m = B.search(1)
    M = B.search(K)
    if P[i-1]+1==m and P[i+K-1]+1>M:
        U.unite(i-1, i)
    B.add(P[i-1]+1, -1)
    B.add(P[i+K-1]+1, 1)
s, l = 0, 1
List = []
for i in range(1, N):
    if P[i-1]<P[i]:
        l+=1
    else:
        if l>=K:
            List.append(s)
        l = 1
        s = i
if l>=K:
    List.append(s)
if len(List)>0:
    s = List[0]
    for i in List[1:]:
        U.unite(s, i)
ans = 0
for i in range(N):
    if U.parent[i] == i:
        ans+=1

print(ans-K+1)

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






A = []
B = []
VA = [0] * n
VB = [0] * n
import heapq
for i in range(k):
    heapq.heappush(A, P[i])  
    heapq.heappush(B, -P[i])  

ans = 1
for i in range(n-k):
    b = -heapq.heappop(B)
    while VB[b] == 1:
        b = -heapq.heappop(B)
    a = heapq.heappop(A)
    while VA[a] == 1:
        a = heapq.heappop(A)
    
    
    if not(P[k+i] > b and P[i] == a):
        ans += 1
        
    heapq.heappush(A, a)
    heapq.heappush(B, -b) 
    heapq.heappush(A, P[k+i])
    heapq.heappush(B, -P[k+i])

    VA[P[i]] = 1
    VB[P[i]] = 1



AA = []
for i in range(n-1):
    if P[i+1] - P[i] >= 0:
        AA.append(1)
    else:
        AA.append(0)
s = sum(AA[:k-1])
t = 0
r = 0
if s == k-1:
    t += 1
    r = 1
for i in range(n-k):
    
    s += AA[k-1+i]
    s -= AA[i]
    if s == k-1:
        t += 1
        r += 1
    else:
        ans += max(0, r-1)
        r = 0
ans += max(0, r-1)

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

Solution (Python):
from heapq import heappush ,heappop
n,k=map(int,input().split())
p=list(map(int,input().split()))
cnt=1
flag=[1]*n
for i in range(1,n):
    if p[i]>p[i-1]:
        cnt+=1
        flag[i]=cnt
    else:
        cnt=1
h=flag.count(k)
if h!=0:
    h-=1
lst_m=[]
lst_M=[]
for i in range(k):
    heappush(lst_m,p[i])
    heappush(lst_M,-p[i])
data_m=[]
data_M=[]
count=0
for i in range(n-k):
    m=lst_m[0]
    M=lst_M[0]
    heappush(lst_m,p[k+i])
    heappush(lst_M,-p[k+i])
    heappush(data_m,p[i])
    heappush(data_M,-p[i])
    if p[i]==lst_m[0]:
        while data_m[0]==lst_m[0]:
            heappop(data_m)
            heappop(lst_m)
            if not data_m:
                break
        if -p[k+i]==lst_M[0]:
            count+=1
    if -p[i]==lst_M[0]:
        while data_M[0]==lst_M[0]:
            heappop(data_M)
            heappop(lst_M)
            if not data_M:
                break
print(n-k+1-count-h)

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

if n == k:
    print(1)
    exit()

def slide_min(n, k, p):
    res = [0] * n
    deq = [0] * n
    s = 0
    t = 0
    for i in range(n):
        while s < t:
            if p[deq[t-1]] >= p[i]:
                t -= 1
            else:
                break
        deq[t] = i
        t += 1
        if i-k+1 >= 0:
            res[i-k+1] = p[deq[s]]
            if deq[s] == i-k+1:
                s += 1
    return res

def slide_max(n, k, p):
    res = [0] * n
    deq = [0] * n
    s = 0
    t = 0
    for i in range(n):
        while s < t:
            if p[deq[t-1]] < p[i]:
                t -= 1
            else:
                break
        deq[t] = i
        t += 1
        if i-k+1 >= 0:
            res[i-k+1] = p[deq[s]]
            if deq[s] == i-k+1:
                s += 1
    return res

s_min = slide_min(n, k, p)
s_max = slide_max(n, k, p)

ans = 1
for i in range(n-k):
    if p[i] > s_min[i] or p[i+k] != s_max[i+1]:
        ans += 1

mode = 0
count = 0
e = 0
for i in range(n-1):
    if p[i] < p[i+1]:
        if mode == 0:
            count = 2
            mode = 1
        else:
            count += 1
    else:
        mode = 0
        if count >= k:
            e += 1
            count = 0

if mode == 1 and count >= k:
    e += 1

if e > 1:
    ans -= e-1

print(ans)

Solution (Python):
class MinSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 >= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                self.start_idx += 1
            else:
                break

    def min(self):
        pos1 = self.pos_list[self.start_idx]
        val1 = self.val_list[pos1]
        return val1

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0
        
    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 <= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                del self.pos_list[self.start_idx]
            else:
                break

    def max(self):
        pos1 = self.pos_list[self.start_idx]
        val1 = self.val_list[pos1]
        return val1




s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 1
ident = True
rv_pos = -1

minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

for i in range(k - 1):
    if p[i] > p[i + 1]:
        rv_pos = i
        ident = False
    
for i in range(k-1):
    minw.put(i)
    maxw.put(i)

for i in range(1,n - k + 1):
    
    maxw.put(i + k - 2)
    minw.put(i + k - 2)
    maxw.get(i-1)
    minw.get(i-1)

    """    
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue
    """
    if p[i + k - 2] > p[i + k - 1]:
        rv_pos = i + k - 2
        

    
    if rv_pos < i:
        if not ident:
            ident = True
            num += 1
        continue
            

    if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
        num += 1

    
print(num)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
p = list(map(int, input().split()))
class SegTree:
  def segfunc(self, x, y):
    u = min(x[0], y[0])
    v = max(x[1], y[1])
    return (u, v) 
  def __init__(self, n, ide_ele, init_val):
    
    self.ide_ele = ide_ele
    
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      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
p = [(x, x) for x in p]
seg = SegTree(N, (float("inf"), 0), p)
mini = [0] * (N - K + 1)
maxi = [0] * (N - K + 1)
for i in range(N - K + 1):
  temp = seg.query(i, i + K)
  mini[i] = temp[0]
  maxi[i] = temp[1]

dcount = 0
alsorted = 0
temp = 0
for i in range(1, N - K + 1):
  if mini[i] != mini[i - 1] and maxi[i] == p[i + K - 1][0]:
    dcount += 1
for i in range(N - 1):
  if p[i][0] < p[i + 1][0]:
    temp += 1
  else: temp = 0
  if temp == K - 1:
    alsorted += 1
if alsorted == 0: alsorted = 1
print(N - K + 1 - dcount - alsorted + 1)

Solution (Python):
class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0-1)

    
    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i+1:
            i = ~-i//2
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

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

RminQ = RangeMinimumQuery(n)
RmaxQ = RangeMinimumQuery(n, func=max, inf=0)

for i, pi in enumerate(p):
    RminQ.update(i, pi)
    RmaxQ.update(i, pi)

a = [1]
for i in range(n-1):
    if p[i] < p[i+1]:
        a.append(a[-1]+1)
    else:
        a.append(1)

ans = n-k+1
flag = a[k-1] == k
for i in range(k, n):
    if (p[i] > RmaxQ.query(i-k+1, i) and p[i-k] < RminQ.query(i-k+1, i)) or (flag and a[i]>=k):
        ans -= 1
    if not flag and a[i] >= k:
        flag = True
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class SegmentTree:
    def __init__(self, init_val, ide_ele, op):
        n = len(init_val)
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        self.op = op
        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.op(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 + 1:
            k = (k - 1) // 2
            self.seg[k] = self.op(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.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res


n, k = LI()
L = LI()
min_ST = SegmentTree(L, INF, min)
max_ST = SegmentTree(L, -INF, max)
cnt = 1
for i in range(n - k):
    if min_ST.query(i, i + k) == L[i] and max_ST.query(i + 1, i + k + 1) == L[i + k]:
        continue
    else:
        cnt += 1


ret = -INF
increasing_block_num = 0
max_len = 0
for j in range(n):
    if L[j] >= ret:
        max_len += 1

    else:
        if max_len >= k:
            increasing_block_num += 1
        max_len = 1
    ret = L[j]


if max_len >= k:
    increasing_block_num += 1



if increasing_block_num:
    print(cnt - (increasing_block_num - 1))
else:
    print(cnt)

Solution (Python):
from collections import deque

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

minList = deque()
maxList = deque()
ascList = deque()


def add_list(_k, target):
    global p
    global minList
    global maxList
    global ascList
    while len(minList) > 0 and p[minList[-1]] >= p[target]:
        minList.pop()
    minList.append(target)
    if minList[0] == target - _k:
        minList.popleft()
    while len(maxList) > 0 and p[maxList[-1]] <= p[target]:
        maxList.pop()
    maxList.append(target)
    if maxList[0] == target - _k:
        maxList.popleft()
    if target > 0 and p[target] < p[target-1]:
        ascList.append(target-1)
    if len(ascList) > 0 and ascList[0] == target - _k:
        ascList.popleft()


count = 0
ascend = 0
for i in range(k):
    add_list(k, i)

if len(ascList) == 0:
    ascend += 1
else:
    count += 1
for i in range(k, n):
    tail_is_max = False
    if p[i] > p[maxList[0]]:
        tail_is_max = True
    add_list(k, i)
    head_is_min = False
    if p[i-k] < p[minList[0]]:
        head_is_min = True
    if not (tail_is_max and head_is_min):
        if len(ascList) == 0:
            if ascend == 0:
                ascend += 1
        else:
            count += 1

print(count+ascend)

Solution (Python):
from sys import stdin
from collections import deque

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = N - K + 1

D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

Q = deque([])
Q_min = []
Q_max = []

for i in range(N):
    while len(Q) > 0 and P[Q[len(Q) - 1]] >= P[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_min.append(P[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

PP = [-x for x in P]
Q = deque([])

for i in range(N):
    while len(Q) > 0 and PP[Q[len(Q) - 1]] >= PP[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_max.append(-PP[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

for i in range(N - K + 1):
    if i > 0:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1

        if (Q_min[i - 1] == P[i - 1] and Q_max[i] == D[-1]) or (oc == K - 1 and ordered_twice):
            ans -= 1

    if oc == K - 1:
        ordered_twice = True

print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
INF = float('inf')
num = 2**(N-1).bit_length()
segmin = [INF] * num*2
segmax = [-INF] * num*2
for i in range(N):
    segmin[num + i - 1] = P[i]
    segmax[num + i - 1] = P[i]
for i in range(num-2, -1, -1):
    segmin[i] = min(segmin[2*i+1], segmin[2*i+2])
    segmax[i] = max(segmax[2*i+1], segmax[2*i+2])

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

ans = 1
for i in range(N-K):
    if not (P[i] < query(segmin, min, INF, i+1, i+K) and P[i+K] > query(segmax, max, -INF, i+1, i+K)):
        ans += 1


combo = 0
nord = 0
for i in range(1,N):
    if P[i] > P[i-1]:
        combo += 1
    else:
        combo = 0
    if combo == K-1:
        nord += 1

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

Solution (Python):
N,K = map(int,input().split())
P = [float('inf')]+list(map(int,input().split()))+[float('inf')]

A = [0]*N
B = [0]*(N+2)
hoge = 1
for i in range(1,N):
    if P[i] < P[i+1]:
        hoge += 1
    else:
        hoge = 1
    if hoge >= K:
        B[i-K+2] = 1
    
for i in range(1,N+1):
    A[P[i]] = i
minL,minR,maxL,maxR = [i-1 for i in range(N+2)],[i+1 for i in range(N+2)],[i-1 for i in range(N+2)],[i+1 for i in range(N+2)]
for i in range(N):
    m = A[i]
    x,y = maxL[m],maxR[m]
    maxL[y] = x
    maxR[x] = y
P[0],P[-1] = -1,-1

for i in range(N-1,-1,-1):
    m = A[i]
    x,y = minL[m],minR[m]
    minL[y] = x
    minR[x] = y
ans = 1
for i in range(1,N-K+1):
    
    L,R = i,i+K
    
    if B[i+1] == 0 and (minR[L] <= R or maxL[R] >= L):
        
        ans += 1


if sum(B) and B[1] == 0:
    ans += 1

print(ans)

Solution (Python):
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class SparseTable:
    """
    構築 O(NlogN)、クエリ O(1)
    """

    def __init__(self, values, fn):
        """
        :param list values:
        :param callable fn: 結合則を満たす冪等な関数。min、max など。add はだめ
        """
        self._values = values
        self._fn = fn

        
        
        self._table = self._build(values, fn)

        
        self._msb = [0] * (len(values) + 1)
        for i in range(2, len(values) + 1):
            self._msb[i] = self._msb[i >> 1] + 1

    @staticmethod
    def _build(values, fn):
        
        size = int(math.log(len(values), 2)) + 1

        st = [[0] * size for _ in range(len(values))]
        for i in range(len(values)):
            st[i][0] = i
        for p in range(1, size):
            for i in range(len(values)):
                q = min(i + (1 << (p - 1)), len(values) - 1)
                l = st[i][p - 1]
                r = st[q][p - 1]
                if values[l] == fn(values[l], values[r]):
                    st[i][p] = l
                else:
                    st[i][p] = r
        return st

    def get(self, a, b):
        """
        半開区間 [a, b) に fn を適用した結果
        :param int a:
        :param int b:
        """
        if b <= a:
            return None
        p = self._msb[b - a]
        return self._fn(
            self._values[self._table[a][p]],
            self._values[self._table[b - (1 << p)][p]]
        )


N, K = list(map(int, sys.stdin.readline().split()))
P = list(map(int, sys.stdin.readline().split()))

dp = [1] * N
for i in range(1, N):
    if P[i - 1] < P[i]:
        dp[i] = dp[i - 1] + 1


ans = N - K + 1

asc_cnt = 0
st_max = SparseTable(P, max)
st_min = SparseTable(P, min)
for r in range(K, N):
    l = r - K
    if st_min.get(l, r) == P[l] and st_max.get(l + 1, r + 1) == P[r]:
        
        ans -= 1
    elif dp[r] >= K:
        
        ans -= 1
        asc_cnt += 1
if dp[K - 1] >= K:
    
    ans -= 1
    asc_cnt += 1

if asc_cnt > 0:
    
    ans += 1
print(ans)

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

def init(init_val):
    for i in range(n):
        MI[i+num-1]=init_val[i]
        MA[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
        MI[i]=min(MI[2*i+1],MI[2*i+2])
        MA[i]=max(MA[2*i+1],MA[2*i+2])
    
def update(k,x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1],MI[k*2+2])
        MA[k] = max(MA[k*2+1],MA[k*2+2])

def rangemin(p,q):
    if q<=p:
        return 1<<100
    p += num-1
    q += num-2
    res= 1<<100
    while q-p>1:
        if p&1 == 0:
            res = min(res,MI[p])
        if q&1 == 1:
            res = min(res,MI[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,MI[p])
    else:
        res = min(min(res,MI[p]),MI[q])
    return res

def rangemax(p,q):
    if q<=p:
        return -1
    p += num-1
    q += num-2
    res= -1
    while q-p>1:
        if p&1 == 0:
            res = max(res,MA[p])
        if q&1 == 1:
            res = max(res,MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,MA[p])
    else:
        res = max(max(res,MA[p]),MA[q])
    return res


num =2**(n-1).bit_length()
MI=[1<<100]*2*num
MA=[-1]*2*num

init(p)
a = 0
l = -1
c = 0
for i in range(1,n):
    if p[i-1] > p[i]:
        a = i
    if i >= k-1 and a <= i-k+1:
        if i-l > 1:
            c += 1
        l= i

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

for i in range(n):
    if i >=k:
        if rangemin(i-k+1,i) < p[i-k] or rangemax(i-k+1,i) > p[i]:
            ans += 1

print(ans)

Solution (Python):
from operator import lt, gt


def hoge(a, K, op):
    from collections import deque
    dq = deque()
    pop, popleft, append = dq.pop, dq.popleft, dq.append

    for i, v in zip(range(K), a):
        while dq and not op(a[dq[-1]], v):
            pop()
        append(i)

    yield a[dq[0]]

    for i in range(K, len(a)):
        while dq and not op(a[dq[-1]], a[i]):
            pop()
        append(i)
        if dq[0] == i-K:
            popleft()
        yield a[dq[0]]


N, K = map(int, input().split())
a = tuple(map(int, input().split()))

inv_flag = [0]*N

for i, (x, y) in enumerate(zip(a, a[1:]), start=1):
    inv_flag[i] = i if x > y else inv_flag[i-1]

min_coro = hoge(a, K, lt)
max_coro = hoge(a, K, gt)

prev_min, prev_max = next(min_coro), next(max_coro)
ans, flag = inv_flag[K-1] != 0, inv_flag[K-1] == 0

for l, r, x, y in zip(range(1, N), range(K, N), min_coro, max_coro):
    if inv_flag[l] == inv_flag[r]:
        flag = 1
    elif not (prev_min < x and prev_max < y):
        ans += 1

    prev_min, prev_max = x, y

print(ans + flag)