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



Sample input:
5 3
0 2 1 4 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
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):
            # 要素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が属するグループとを併合する
            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):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素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):
            # 要素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):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            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])

        # 値xに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)
    D = defaultdict(str)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            D[i] = "L"
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            D[i+K-1] = "R"
    #print(D)
    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)
    #print(skip)
    #print(bigger)
    for i in range(len(skip)-1):
        uf.unite(skip[i],skip[i+1])

    for i in range(N-K):
        if D[i]=="L" and D[i+K]=="R":
            uf.unite(i,i+1)

    ans = set()
    for i in range(N-K+1):
        cur = uf.find(i)
        #print(i,cur)
        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
"""

Submission status: Wrong Answer

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

def examB():
    class segment_():
        def __init__(self, A, n, segfunc,ide_ele):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            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])

        # 値xに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)
    D = defaultdict(str)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            D[i] = "L"
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            D[i+K-1] = "R"
    #print(D)
    ans = N-K+1
    bigger = [False]*N
    skip = defaultdict(bool)
    n = 0
    for i in range(N-1):
        if P[i+1]>P[i]:
            bigger[i] = True
    cur = sum(bigger[:K-1])
    if cur == K - 1:
        # print(i,cur)
        skip[0] = True
        n += 1
    for i in range(N-K):
        if bigger[i+K-1]:
            cur += 1
        if bigger[i]:
            cur -= 1
        if cur==K-1:
            #print(i,cur)
            skip[i+1] = True
            n += 1
    #print(skip)
    #print(bigger)
    #print(ans)
    if n>=2:
        ans -= (n-1)
    for i in range(N-K):
        if skip[i]:
            continue
        if D[i]=="L" and D[i+K]=="R":
            ans -= 1
    print(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()

"""

"""

Submission status: Wrong Answer

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

def examB():
    class segment_():
        def __init__(self, A, n, segfunc,ide_ele):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            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])

        # 値xに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)
    D = defaultdict(str)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            D[i] = "L"
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            D[i+K-1] = "R"
    #print(D)
    ans = N-K+1

    bigger = [False]*N
    cur = 0
    skip = defaultdict(bool)
    flag = False
    n = 0
    for i in range(N-1):
        if P[i+1]>P[i]:
            bigger[i] = True
        if bigger[i]:
            cur += 1
        if bigger[i-K+1]:
            cur -= 1
        if cur==K-1:
            #print(i,cur)
            skip[i-K+1] = True
            n += 1
    #print(bigger)
    #print(ans)
    if n>=2:
        ans -= (n-1)
    for i in range(N-K):
        if skip[i]:
            continue
        if D[i]=="L" and D[i+K]=="R":
            ans -= 1
    print(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()

"""

"""

Submission status: Wrong Answer

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

def examB():
    class segment_():
        def __init__(self, A, n, segfunc,ide_ele):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            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])

        # 値xに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)
    D = defaultdict(str)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            D[i] = "L"
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            D[i+K-1] = "R"
    #print(D)
    bigger = [False]*N
    cur = 0
    skip = defaultdict(bool)
    flag = False
    ans = 1
    for i in range(N-1):
        if P[i+1]>P[i]:
            bigger[i] = True
        if bigger[i]:
            cur += 1
        if bigger[i-K+1]:
            cur -= 1
        if cur==K-1:
            #print(i,cur)
            skip[i-K+1] = True
    #print(bigger)
    #print(ans)
    for i in range(N-K):
        if D[i]=="L" and D[i+K]=="R":
            continue
        if skip[i]:
            if not flag:
                flag = True
                ans += 1
            continue
        ans += 1
    print(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()

"""

"""

Submission status: Wrong Answer

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

def examB():
    class segment_():
        def __init__(self, A, n, segfunc,ide_ele):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            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])

        # 値xに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)
    D = defaultdict(str)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            D[i] = "L"
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            D[i+K-1] = "R"
    #print(D)
    ans = 2
    bigger = [False]*N
    cur = 0
    for i in range(N-1):
        if P[i+1]>P[i]:
            bigger[i] = True
        if bigger[i]:
            cur += 1
        if bigger[i-K+1]:
            cur -= 1
        if cur==K-1:
            #print(i,cur)
            ans -= 1
    #print(bigger)
    if ans==2:
        ans -= 1
    for i in range(N-K):
        if D[i]=="L" and D[i+K]=="R":
            continue
        ans += 1
    print(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()

"""

"""

Submission status: Wrong Answer

Solution code:
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)
answer = 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:
    answer -= 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])  
  answer += 1

if N != K and sorted(A[N - K:]) == A[N - K:]:
  answer -= 1
  
print(answer)

Submission status: Wrong Answer

Solution code:
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 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 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)

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_right
import heapq,copy
def checkMax(i,j):
    amax = [1000,0]
    while Kmax:
        amax = heapq.heappop(Kmax)
        if amax[1]>=j:break
    amax[0] = -amax[0]
    if i-j==K:
        if P[i]>amax[0]:
            if amax[1]>0:
                amax[0] = -amax[0]
                heapq.heappush(Kmax,amax)
            return True
        else:
            if amax[1]>0:
                amax[0] = -amax[0]
                heapq.heappush(Kmax,amax)
            return False
    else:
        if P[i]>amax[0] or (P[i]==amax[0] and i==amax[1]):
            if amax[1]>0:
                amax[0] = -amax[0]
                heapq.heappush(Kmax,amax)
            return True
        else:
            if amax[1]>0:
                amax[0] = -amax[0]
                heapq.heappush(Kmax,amax)
            return False
def checkMin(i,j):
    amin = [10**6,0]
    while Kmin:
        amin = heapq.heappop(Kmin)
        if i<=amin[1]<=j:break
    if P[i]<amin[0] or (P[i]==amin[0] and i==amin[1]):
        if amin[1]>0:
            heapq.heappush(Kmin,amin)
        return True
    else:
        if amin[1]>0:
            heapq.heappush(Kmin,amin)
        return False
N,K = map(int,input().split())
P = list(map(int,input().split()))
Lmax = deque([])
Lmin = deque([])
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
A = copy.deepcopy(Lmax)
B = copy.deepcopy(Lmin)
Kmax = []
Kmin = []
flgmax = 0
flgmin = 0
while flgmax*flgmin==0:
    if len(Lmax)>0 and Lmax[0][0]<K:
        amax = Lmax.popleft()
        heapq.heappush(Kmax,[-amax[1],amax[0]])
    else:
        flgmax = 1
    if len(Lmin)>0 and Lmin[0][0]<K:
        amin = Lmin.popleft()
        heapq.heappush(Kmin,[amin[1],amin[0]])
    else:
        flgmin = 1
cnt = 0
flagMono = 0
indmin = bisect_right(B,[K-1,P[K-1]])
if checkMin(0,K-1) and checkMax(K-1,0) and (len(B)==0 or B[indmin-1][0]==0):
    if flagMono==0:
        flagMono=1
        cnt += 1
    else:
        pass
elif K<N and checkMax(K,0) and checkMin(0,K-1) and P[0]<P[K]:
    pass
else:
    cnt += 1
for i in range(1,N-K+1):
    if len(Lmax)>0 and Lmax[0][0]<i+K:
        a = Lmax.popleft()
        heapq.heappush(Kmax,[-a[1],a[0]])
    if len(Lmin)>0 and Lmin[0][0]<i+K:
        a = Lmin.popleft()
        heapq.heappush(Kmin,[a[1],a[0]])
    indmin = bisect_right(B,[i+K-1,P[i+K-1]])
    if checkMin(i,i+K-1) and checkMax(i+K-1,i) and (len(B)==0 or B[indmin-1][0]<=i):
        if flagMono==0:
            flagMono = 1
            cnt += 1
        else:
            pass
    elif i+K<N and checkMax(i+K,i) and checkMin(i,i+K-1) and P[i+K]>P[i+K-1]:
        continue
    else:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input
class Sparse_Table():
    def __init__(self, arr, fn):
        from math import log2,ceil
        self.arr=arr
        self.n=len(arr)
        self.logfn=log2
        self.ceilfn=ceil
        self.table=self.build(fn)
    def build(self, fn):

        n=self.n
        sz=int(self.logfn(n))+1
        self.column_length=sz
        st=[[-1 for i in range(sz)] for j in range(n)]
        for i in range(n):
            st[i][0]=self.arr[i]
        for i in range(1,sz):
            step=pow(2,i-1)
            for j in range(n-step*2+1):
                st[j][i]=fn(st[j+step][i-1], st[j][i-1])
            
        return st
    
    def query(self,l,r):
        #0<=l<=r<=n-1
        #returns index pos
        #print(l,r)
        if l<0 or r>=self.n:
            raise IndexError("invalid range")
        if l==r:return self.table[l][0]
        else:
            df=r-l+1
            df0=int(self.logfn(df))
            df1=pow(2,df0)
            #print(l,r,df0)
            s1=self.table[l][df0]
            if df1<df:
                s2=self.query(l+df1,r)
                return s1+s2
            else:
                return s1

def main():
    n, k = lin()
    a  = lin()
    mxa = Sparse_Table(a, lambda x,y: max(x, y))
    mna = Sparse_Table(a, lambda x,y: min(x, y))
    print('CHECK', mxa.query(1, n-1), mna.query(1, n-1))
    ans = 1
    for i in range(k, n):
        l, r= i-k+1, i-1
        mn = mna.query(l, r)
        mx = mxa.query(l, r)
        # print(l, r, mx, mn)
        if mn<a[l-1] or mx>a[i]:
            ans+=1
    print(ans)





        
main()
#threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input
def main():
    n, k = lin()
    a  = lin()
    ans = 1
    ch = []
    l, r=0, 0
    for i in range(1, k):
        if a[i-1]>a[i]:
            ch.append(i-1)
            r+=1
    a1 = set()
    for i in range(k, n):
        # print(ch[l:r])
        ch1 = 0
        if r-l:
            while l<r and ch[l]<=i-k:
                l+=1
                ch1 = 1
        if a[i-1]>a[i]:
            # print('ADD', i-1)
            ch.append(i-1)
            r+=1
            ans += 1
        else:
            if l :a1.add(l)
        # print(ch[l:r], i, ans)
    print(ans+len(a1))





        
main()
#threading.Thread(target=main).start()

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input
def main():
    n, k = lin()
    a  = lin()
    ans = 1
    ch = []
    l, r=0, 0
    for i in range(1, k):
        if a[i-1]>a[i]:
            ch.append(i-1)
            r+=1
    for i in range(k, n):
        # print(ch[l:r])
        ch1 = 0
        if r-l:
            while l<r and ch[l]<=i-k:
                l+=1
                ch1 = 1
        if a[i-1]>a[i]:
            # print('ADD', i-1)
            ch.append(i-1)
            r+=1
            ans += 1
        else:
            ans += 1 if ch1 else 0  

        # print(ch[l:r], i, ans)
    print(ans)





        
main()
#threading.Thread(target=main).start()