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:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())
min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

ans = 1
min_out_flag = False
for i in range(n - k):
    if P[i:i + k] != sorted(P[i:i + k]):
        if not (min_out_flag and P[i + k - 1] == max_seg.query(i, i + k)):
            ans += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1

# 変化しないものを数える
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]

for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1

C = Counter(LIS[:N - K + 1])
for k, v in C.items():
    if k == 1:
        continue
    else:
        ans -= v * (v - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1

# 変化しないものを数える
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]

for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1

C = Counter(LIS[:N - K + 1])
for k, v in C.items():
    if k == 1:
        continue
    else:
        ans -= v - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


class SegmentTreeRMQ(object):  # 1-indexed [l,r)
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):  # 0-indexed
        i += self.len
        while i > 0:
            self.array[i] = min(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):  # 0-indexed
        return self.array[i + self.len]

    def get_minimum(self, l, r):  # 0-indexed
        L = l+self.len
        R = r+self.len
        ANS = 1 << 30

        while L < R:
            if L & 1:
                ANS = min(ANS, self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = min(ANS, self.array[R])
            L >>= 1
            R >>= 1

        return ANS


N, K = na()
P = na()

if N == K or N == 2:
    print(1)
    exit()


min_tree = SegmentTreeRMQ(N, N)
max_tree = SegmentTreeRMQ(N, 1)

for i, p in enumerate(P):
    min_tree.update(i, p)
    max_tree.update(i, -p)

no_change = [0] * (N-K+1)

last = -1

for i in range(N):
    if i - last >= K:
        no_change[i-K+1] = 1
    if i == N-1:
        break
    if P[i] > P[i+1]:
        last = i

# print(no_change)


ans = 1
no_count = 0

for i in range(N-K):
    if P[i] > min_tree.get_minimum(i+1, i+K+1) or -P[i+K] > max_tree.get_minimum(i+1, i+K+1):
        ans += 1
        if no_change[i] == 1 or (i == (N-K-1) and no_change[N-K] == 1):
            no_count += 1


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

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

class SegminTree:
    # init_valはseg木にしたいlist、ide_eleは単位元
    # """
    # 単位元の説明
    # 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
    # 　　和のセグ木 → 0　(上の単位元の説明を参照)
    # 　　積のセグ木 → 1　(上の単位元の説明を参照)
    # 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
    # """
    def __init__(self, init_val, ide_ele):
        self.ide_ele=ide_ele
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1]=init_val[i]
        #built
        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 segfunc(self, x, y):
        return min(x,y)
    
    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

class SegmaxTree:
    # init_valはseg木にしたいlist、ide_eleは単位元
    # """
    # 単位元の説明
    # 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
    # 　　和のセグ木 → 0　(上の単位元の説明を参照)
    # 　　積のセグ木 → 1　(上の単位元の説明を参照)
    # 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
    # """
    def __init__(self, init_val, ide_ele, func):
        self.ide_ele=ide_ele
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
        self.func=func

        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1]=init_val[i]
        #built
        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 segfunc(self, x, y):
        return self.func(x,y)
    
    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

segmin=SegminTree(p,10**9)
segmax=SegmaxTree(p,0,max)

lst=[]
for i in range(n-k+1):
    tmp1=segmin.query(i,k+i)
    tmp2=segmax.query(i,k+i)
    lst.append((tmp1,tmp2))
# print(lst)

ans=1
for i in range(n-k):
    # print(lst[i][0],p[i])
    # print(lst[i+1][1],p[i+k])
    if lst[i][0]==p[i] and lst[i+1][1]==p[i+k]:
        continue
    else:
        ans+=1
# print(ans)

cnt=1
cnt2=0
for i in range(n-1):
    if p[i]<p[i+1]:
        cnt+=1
    else:
        cnt=1
    if cnt>=k:
        cnt2+=1
# print(cnt2)
if cnt2>=2:
    print(ans-cnt2+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
change = []
for i in range(n - 1):
    change.append(p[i + 1] > p[i])
ans = 0 
for i in range(n - k + 1):
    if i == 0:
        ans += 1
        continue
    if i < n - k - 1:
        if (change[i - 1]) & (change[i + k - 2]):
            continue
        ans += 1
    else:
        if change[i - 1]:
            continue
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import add
import sys
input=sys.stdin.readline


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 # 処理(add or xor max minなど)

    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):
        # [l, r) についてqueryを求める
        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 = [0]+list(map(int, input().split()))
tree = SegTree(N+1, 0, min)

for i in range(1, N+1):
    tree.update(i, P[i]-P[i-1])

ans = 0
isOrig = 0
for i in range(0, N-K+1):
    v = tree.get(i+1, i+K)
    if v>=0:
        isOrig = 1
    else:
        ans += 1
print(ans+isOrig)

Submission status: Wrong Answer

Solution code:
from operator import add
import sys
input=sys.stdin.readline


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 # 処理(add or xor max minなど)

    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):
        # [l, r) についてqueryを求める
        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 = [0]+list(map(int, input().split()))
tree = SegTree(N+1, 0, min)

for i in range(1, N+1):
    tree.update(i, P[i]-P[i-1])

ans = 0
for i in range(0, N-K+1):
    ans += tree.get(i+1, i+K)<0
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import add
import sys
input=sys.stdin.readline


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 # 処理(add or xor max minなど)

    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):
        # [l, r) についてqueryを求める
        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())
tree = SegTree(N, 0, add)
ans = 0
for i, j in enumerate(P):
    tree.update(j, 1)
    ans += i-tree.get(0, j)
print(ans if ans!=0 else 1)

Submission status: Wrong Answer

Solution code:
1

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

ans=1
# dic=set()
for i in range(n-k):
    # print(p[i],min(p[i:i+k]),p[i+k],max(p[i+1:i+k+1]))
    # tmp=tuple(p[:i]+sorted(p[i:i+k])+p[i+k:])
    # print(tmp)
    # if tmp in dic:
    #     print(i,tmp)
    # dic.add(tmp)
    # print(set)
    # print()
    if p[i]==min(p[i:i+k]) and p[i+k]==max(p[i+1:i+k+1]):
        pass
    else:
        ans+=1
# tmp=tuple(p[:i+1]+sorted(p[i+1:i+k+1])+p[i+k+1:])
# dic.add(tmp)
# print(len(dic))
cnt=0
same=0
for i in range(n-1):
    if p[i+1]>p[i]:
        cnt+=1
    else:
        cnt=0
    if cnt>=k-1:
        same+=1
    # print(i,cnt,same)
# print(same)
if same>=2:
    ans-=same-1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)
 
from collections import deque
N, K = mapint()
Ps = list(mapint())
Q = deque()
min_lis = []
max_lis = []
for i in range(N):
    if not Q:
        Q.append(i)
        min_lis.append(Ps[Q[0]])
    else:
        while Q:
            q = Q.pop()
            if Ps[i]>Ps[q]:
                Q.append(q)
                break
        Q.append(i)
        if Q[0]==i-K-1:
            Q.popleft()
        min_lis.append(Ps[Q[0]])
Q = deque()
for i in range(N):
    if not Q:
        Q.append(i)
        max_lis.append(Ps[Q[0]])
    else:
        while Q:
            q = Q.pop()
            if Ps[i]<Ps[q]:
                Q.append(q)
                break
        Q.append(i)
        if Q[0]==i-K-1:
            Q.popleft()
        max_lis.append(Ps[Q[0]])
ans = 0
flg = 0
for i, (mi, ma) in enumerate(zip(min_lis[K+1:], max_lis[K+1:]), K+1):
    if mi==Ps[i-K-1] and ma==Ps[i]:
        flg = 1
        continue
    ans += 1
if ans==0: flg=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from itertools import accumulate
from bisect import bisect_left, bisect_right
N, K = mapint()
Ps = list(mapint())
Incr = [0]
cnt = 1
for i in range(1, N):
    if Ps[i-1]>Ps[i]:
        Incr.append(cnt)
        cnt = 1
    else:
        cnt += 1
Incr.append(cnt)
ans = 0
cum = list(accumulate(Incr))
now_idx = 1
for i in range(N-K):
    now_idx = bisect_right(cum, i)
    if now_idx!=bisect_left(cum, i+K):
        ans += 1
if max(Incr)>=K:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    Ps = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    bit=BIT(N+1)
    sc=1
    tot=0
    j=0
    cur=Ps[0]
    count=0
    for p in Ps[:K]:
        bit.add(p+1,1)
    for i in range(N-K+1):
        if cur<=Ps[i]:
            if i-j+1>=K:
                if count>0:
                    sc=0
                else: count=1
        else:
            j=i
        cur=Ps[i]

        tot+=sc
        if i==N-K:
            break
        a=Ps[i]
        b=Ps[i+K]
        if bit.find_kth_element(1)==a+1 and bit.find_kth_element(K)<=b+1:
            sc=0
        else:
            sc=1
        bit.add(a+1,-1)
        bit.add(b+1,1)
    
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    Ps = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    bit=BIT(N+1)
    sc=1
    tot=0
    j=0
    cur=Ps[0]
    count=0
    for p in Ps[:K]:
        bit.add(p+1,1)
    for i in range(N-K+1):
        if cur<=Ps[i]:
            if i-j+1>=K and count>0:
                sc=0
            count=1
        else:
            j=i
        cur=Ps[i]

        tot+=sc
        if i==N-K:
            break
        a=Ps[i]
        b=Ps[i+K]
        if bit.find_kth_element(1)==a+1 and bit.find_kth_element(K)<=b+1:
            sc=0
        else:
            sc=1
        bit.add(a+1,-1)
        bit.add(b+1,1)
    
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    Ps = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    bit=BIT(N+1)
    sc=1
    tot=0
    scs=[1]*(N-K+1)
    for p in Ps[:K]:
        bit.add(p+1,1)
    include_sorted=1
    for i in range(N-K):
        tot+=sc
        a=Ps[i]
        b=Ps[i+K]
        if bit.find_kth_element(1)==a+1 and bit.find_kth_element(K)<=b+1:
            sc=0
        else:
            sc=1
        bit.add(a+1,-1)
        bit.add(b+1,1)
    i=N-K
    tot+=sc
    i=1
    j=0
    cur=Ps[0]
    count=0
    while i<N:
        if cur<=Ps[i]:
            if i-j+1>=K:
                count+=1
        else:
            j=i
        cur=Ps[i]
        i+=1
    print(tot-count+1)


if __name__ == "__main__":
    main()