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:
import sys
import heapq

input = sys.stdin.readline

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

hq = []
for i in range(K):
    heapq.heappush(hq, P[i])

res = 1
for i in range(1,N-K):
    pre_min = heapq.heappop(hq)
    pre_max = hq[-1]
    heapq.heappush(hq, P[i+K-1])

    if hq[-1] != pre_max:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
p = list(map(int, input().split()))
pSum = 0
swi = 0
for i in range(n-k+1):
    if p[i:i+k] != sorted(p[i:i+k]):
        pSum += 1
    else:
        swi = 1
print(pSum + swi)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        P = list(map(int, input().split()))

        sorted_p = sorted(P)
        diff = ''
        for i in range(N):
            if P[i] != sorted_p[i]:
                diff += '1'
            else:
                diff += '0'
        ans = 0
        print(1)
        # for i in range(N - K):
        #     if int(diff[i:i + K], 2) > 0:
        #         ans += 1
        # print(max(1, ans))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
if N == K:
    print(1)
    exit()
P = list(map(int,input().split()))
s = sorted(range(len(P)), key=lambda k: P[k])
P = sorted(range(len(s)), key=lambda k: s[k])
count=0

m = min(P[ : K])
M = max(P[ : K])
for i in range(N-K+1):
    if m == P[i] and M < P[i+K+1]:
        M = P[i+K+1]
        m = min(P[i : i+K])
        continue
    else:
        count+=1
print(count)

Submission status: Wrong Answer

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

sa=n-k
temp=p[0:k+1]
m=max(temp)
n=min(temp)
mdex=temp.index(m)
ndex=temp.index(n)
ans=1

if(sa==0):

    ans=1

elif(sa==1):
    m=max(p)
    n=min(p)
    mdex=p.index(m)
    ndex=p.index(n)
    ans=2
    if(mdex!=n-1 or ndex!=0):
        ans=1

elif(sa>1):
    for i in range(1,sa):
        shin=p[k+i]
        if(shin>m):
            m=shin
            mdex=k+i
        elif(shin<n):
            n=shin
            ndex=k+i
        elif(mdex==i-1 or ndex==i-1):
            temp=p[i:k+i+1]
            m=max(temp)
            n=min(temp)
            mdex=temp.index(m)
            ndex=temp.index(n)
        ans+=1
        if(ndex==i and mdex==k+i):
            ans-=1

print(ans)

Submission status: Wrong Answer

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

ans=0
flag = False
sorted_f = False
for i in range(N-K+1):
  if flag:
    flag=False
    continue
    
  if i != N - K and min(P[i:i+K])==P[i] and max(P[i+1:i+K+1]) == P[i+K]:
    flag=True
  for j in range(K-1):
    if P[i+j]> P[i+j+1]:
      break
    elif j == K-2:
      if sorted_f:
        ans -= 1
      else:
        sorted_f = True
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        P = list(map(int, input().split()))

        sorted_p = sorted(P)
        print(1)
        # cnt = 0
        # diff = ''
        # for i in range(N):
        #     if P[i] != sorted_p[i]:
        #         cnt += 1
        #         diff += '1'
        #     else:
        #         diff += '0'
        # ans = 0
        # for i in range(N - K):
        #     if int(diff[i:i + K], 2) > 0:
        #         ans += 1
        # print(max(1, ans))


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p1=[int(i) for i in input().split()]
p2=[0]*(n-1)
j=1
for i in range(n-1):
    if p1[i]>p1[i+1]:
        p2[i]=j
        j+=1
#print(p2)
x=p2[:k-1]
s1=sum(x)
j=1
for i in range(n-k):
    s2=s1-p2[i]+p2[i+k-1]
    if s1!=s2 and (s1!=0 or s2!=0):
        j+=1
        #print(i)
    s1=s2
print(j)

Submission status: Wrong Answer

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

count=0
mx=-1
buf=max(p[0:k])
s=1
for i in range(n-1):
    if p[i]>p[i+1]:
        s=1
    else:
        s+=1
        if s==k:
            count+=1
            break
if i!=k-2:
    count+=1

for i in range(1,n-k+1):
    mx=max(p[i:k+i-1])
    if p[i+k-1]<mx:
        count+=1
    elif buf>mx:
        count+=1
    buf=mx
print(count)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
cnt = 0 #ダブ1種
cnt2 = -1 #ダブ2種

for i in range(0,n-k):
    if p[i] < p[i+1]:
        if min(p[i:i+k]) == p[i]:
            if max(p[i+1:i+k+1]) == p[i+k]:
                cnt += 1
            elif sorted(p[i:i+k]) == p[i:i+k]:
                cnt2 += 1

if cnt2 > 0:
    ans = n-k+1-cnt-cnt2
else:
    ans = n-k+1-cnt
    

print(ans)

Submission status: Wrong Answer

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

maxs=[1]*(N-K+1)
m=max(P[:K])
for i in range(1, N-K):
  if P[i+K-1]>=m:
    maxs[i]=0
    m=P[i+K-1]
    
mins=[1]*(N-K+1)
m=min(P[-K:])
for i in range(N-K, -1, -1):
  if P[i-1]<=m:
    mins[i]=0
    m=P[i-1]
    
counter=0
for i in range(N-K+1):
  if mins[i]==0 and maxs[i]==0:
    pass
  else:
    counter+=1
    
dif=[P[i]-P[i-1] for i in range(1, N)]
counter2=0
while i<N-K+1:
  res=1
  for j in range(K-1):
    if dif[i+j]<0:
      res=0
  if res==1:
    counter2+=1
    i=i+K-1
  else:
    i+=1

if counter2>1:
  counter=counter-counter2+1
  
print(counter)

Submission status: Wrong Answer

Solution code:
class Min_seg:
    def __init__(self,n,init_val,ide_ele = 10**9):
        # set_val
        self.ide_ele = ide_ele #単位元
        self.n = n #要素数
        self.num = 2 ** (self.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]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = min(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] = min(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 = min(res, self.seg[p])
            if q & 1 == 1:
                res = min(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = min(res, self.seg[p])
        else:
            res = min(min(res, self.seg[p]), self.seg[q])
        return res

class Max_seg:
    def __init__(self,n,init_val,ide_ele = 0):
        # set_val
        self.ide_ele = ide_ele #単位元
        self.n = n #要素数
        self.num = 2 ** (self.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]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = max(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] = max(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 = max(res, self.seg[p])
            if q & 1 == 1:
                res = max(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = max(res, self.seg[p])
        else:
            res = max(max(res, self.seg[p]), self.seg[q])
        return res

n,k = map(int,input().split())
p = list(map(int,input().split()))
seg1 = Min_seg(n,p)
seg2 = Max_seg(n,p)

ans = n-k+1
for i in range(n-k):
    #print(0,p[i],seg1.query(i,i+k-1))
    #print(1,p[i+k],seg2.query(i+1,i+k+1))
    if p[i] == seg1.query(i,i+k-1) and p[i+k] == seg2.query(i+1,i+k+1):
        ans -= 1

#print(ans,"試し")

d = [0 for _ in range(n-1)]
for i in range(n-1):
    if p[i] < p[i+1]:
        d[i] = 1

seg3 = Min_seg(n-1,d)
data = [seg3.query(i,i+k-1) for i in range(n-k+1)]
#print(data)


if k > 2 and sum(data) > 1:
    now = -1
    for i in range(n-k+1):
        if data[i] == 1:
            if i == 0:now += 1
            elif data[i-1] == 0:now += 1
    ans -= now

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heapify, heappop, heappush
def main():
    N, K = map( int, input().split())
    P = list( map( int, input().split()))
    ans = 0
    now = -1
    cnt = 1
    CNT = [0]*N
    for i in range(N-1,-1,-1):
        p = P[i]
        if p < now:
            cnt += 1
        else:
            cnt = 1
        now = p
        if cnt >= K:
            CNT[i] = 1
    if sum(CNT) > 0:
        ans = 1
            
    for i in range(K-1):
        if P[i] > P[i+1]:
            ans += 1
            break
    Max = [ -P[i] for i in range(K)]
    Min = [ P[i] for i in range(K)]
    heapify(Max)
    heapify(Min)
    C = [0]*N
    for i in range(K, N):
        while C[Min[0]] == 1:
            heappop(Min)
        while C[Max[0]] == 1 or Max[0] == P[i-K]:
            heappop(Max)
#        print(P[i+1-K])
#        print(P[i-K], Min[0], P[i] , -Max[0])
        if CNT[i+1-K] == 1:
            pass
        elif P[i-K] == Min[0] and P[i] > -Max[0]:
            pass
        else:
            ans += 1
        C[P[i-K]] = 1
        heappush(Min, P[i])
        heappush(Max, -P[i])
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if k == n:
    print('1')
    exit()
ans = 1
irekawaranai = 0

minl = [0]*(n-k+1)
maxl = [0]*(n-k+1)
tmpmin = min(p[:k])
tmpmax = max(p[:k])
for i in range(k, n):
    minl[i-k] = tmpmin
    maxl[i-k] = tmpmax
    if p[i] > tmpmax:
        tmpmax = p[i]
    elif p[i] < tmpmin:
        tmpmin = p[i]
    if p[i-k] > tmpmax:
        tmpmax = max(p[i-k+1:i+1])
    elif p[i-k] < tmpmin:
        tmpmin = min(p[i-k+1:i+1])



for i in range(n-k):
    if p[i] == minl[i] and maxl[i] < p[i+k]:
      	pass
    elif p[i+1] == minl[i] and maxl[i] < p[i+k]:
        irekawaranai += 1
    else:
        ans += 1
if irekawaranai > 0:
    ans -= irekawaranai - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # l=[i for i in range(1,2001)]
  # print(' '.join([str(x) for x in l]))
  n,k=LI()
  l=LI()

  ans=0
  a=l[:k]
  sort_a=a.sort()
  if a!=sort_a:
    ans+=1

  j=0
  for i in range(k,n):
    b=l[i]
    c=bisect.bisect_right(a,b)
    if c!=k:
      ans+=1
    a.insert(c,b)


  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # l=[i for i in range(1,2001)]
  # print(' '.join([str(x) for x in l]))
  n,k=LI()
  l=LI()

  ans=0
  a=l[:k]
  sort_a=a.sort()
  if a!=sort_a:
    ans+=1

  j=0
  for i in range(k,n):
    b=l[i]
    c=bisect.bisect_right(a,b)


  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
N,K = map(int,input().split())
P = list(map(int,input().split()))

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

skip = [-1,-1]
flg = False
for i in range(N):
	if upper[N-i-1] >= K:
		skip.append(N-i-1)

skip.pop()
deq_min = deque([P[0]])
deq_max = deque([P[0]])
minlen = 1
maxlen = 1
for i in range(1, K):
	while minlen > 0 and deq_min[-1] > P[i]:
		deq_min.pop()
		minlen -= 1
	deq_min.append(P[i])
	minlen += 1
	while maxlen > 0 and deq_max[-1] < P[i]:
		deq_max.pop()
		maxlen -= 1
	deq_max.append(P[i])
	maxlen += 1

ans = 1
next_skip = skip.pop()
for i in range(1, N-K+1):
	new_i = i+K-1
	min_rem = (deq_min[0] == P[i-1])
	max_add = (deq_max[0] < P[new_i])
	if not (min_rem and max_add):
		if i != next_skip:
			ans += 1
	if i == next_skip:
		next_skip = skip.pop()
	if min_rem:
		deq_min.popleft()
		minlen -= 1
	while minlen > 0 and deq_min[-1] > P[new_i]:
		deq_min.pop()
		minlen -= 1
	deq_min.append(P[new_i])
	minlen += 1
	while maxlen > 0 and deq_max[-1] < P[new_i]:
		deq_max.pop()
		maxlen -= 1
	deq_max.append(P[new_i])
	maxlen += 1
print(ans)

Submission status: Wrong Answer

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.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 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
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,K=map(int,input().split())
P=[int(i) for i in input().split()]
mintree=segtree(P,min,N)
maxtree=segtree(P,max,-1)
G=UnionFind(N-K+1)
for i in range(N-K):
    m=mintree.query(i+1,i+K)
    M=maxtree.query(i+1,i+K)
    #print(m,M)
    if P[i]<m and M<P[i+K]:
        G.unite(i,i+1)
aaa=[G.find(i) for i in range(N-K+1)]
Q=[1 for i in range(N)]
for i in range(N-1):
    if P[i]<P[i+1]:
        Q[i+1]=Q[i]+1
    else:
        Q[i+1]=1
tmp=0
for i in range(N):
    if Q[i]>=K:
        tmp+=1
if tmp>0:
    tmp-=1
print(len(set(aaa))-tmp)

Submission status: Wrong Answer

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

maxs=[1]*(N-K+1)
m=max(P[:K])
for i in range(1, N-K):
  if P[i+K-1]>=m:
    maxs[i]=0
    m=P[i+K-1]
    
mins=[1]*(N-K+1)
m=min(P[-K:])
for i in range(N-K, -1, -1):
  if P[i-1]<=m:
    mins[i]=0
    m=P[i-1]
    
counter=0
for i in range(N-K+1):
  if mins[i]==0 and maxs[i]==0:
    pass
  else:
    counter+=1
    
dif=[P[i]-P[i-1] for i in range(1, N)]
counter2=0
for i in range(N-K+1):
  res=1
  for j in range(K-1):
    if dif[i+j]<0:
      res=0
  if res==1:
    counter2+=1

if counter2>1:
  counter=counter-counter2+1
  
print(counter)

Submission status: Wrong Answer

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


n, k = LI()
L = LI()
l = 0
r = k
cnt = 1
for l in range(n - k):
    if L[l] > L[l + 1] or L[l + k - 1] > L[l + k]:
        cnt += 1


print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
num,div= input().split()
num = int(num)
div = int(div)
ar = np.array(list(map(int, input().split())))
box = [str(np.hstack((np.sort(ar[:div]),ar[div:]))),str(np.hstack((ar[:div],np.sort(ar[div:]))))]
for i in range(1,num-div-1):
  box.append(str(np.hstack((ar[:i],np.sort(ar[i:i+div]),ar[i+div:]))))
print(len(np.unique(box)))

Submission status: Wrong Answer

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

tmp = []
left = 999999
right = 999999
ans = N - K + 1
for idx, val in enumerate(P):
    if idx == N - K + 1:
        break
    if P[idx] > left and P[idx + K - 1] > right:
        ans -= 1
    left = P[idx]
    right = P[idx + K - 1]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = 1
c = 0
d = 0
q = deque()
p = deque()
for i in range(K):
    if len(q) == 0:
        q.append(i)
    else:
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
            else:
                q.append(i)
                break
        else:
            q.append(i)

    if len(p) == 0:
        p.append(i)
    else:
        while len(p) > 0:
            if a[p[len(p)-1]] < a[i]:
                p.pop()
            else:
                p.append(i)
                break
        else:
            p.append(i)
    if len(q) == K:
        c += 1

for i in range(K, N):
    if len(q) == 0:
        q.append(i)
    else:
        flag = 0
        while len(q) > 0:
            if a[q[len(q)-1]] > a[i]:
                q.pop()
                flag = 1
            else:
                q.append(i)
                break
        else:
            q.append(i)
        if q[0] == i-K:
            l = q.popleft()
        else:
            flag = 1

    if len(p) == 0:
        p.append(i)
    else:
        while len(p) > 0:
            if a[p[len(p)-1]] < a[i]:
                p.pop()
            else:
                p.append(i)
                break
        else:
            p.append(i)
        if a[p[0]] > a[i]:
            flag = 1

        if p[0] == i-K:
            l = p.popleft()



    if flag == 1:
        ans += 1
    if len(q) == K and flag == 1:
        c += 1
    print(q)

if c > 1:
    ans -= c-1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
cnt = 0 #ダブ1種
cnt2 = -1 #ダブ2種

for i in range(0,n-k):
    if p[i] < p[i+1]:
        if min(p[i:i+k]) == p[i]:
            if max(p[i+1:i+k+1]) == p[i+k]:
                cnt += 1
            elif sorted(p[i:i+k]) == p[i:i+k]:
            	cnt += 1

if cnt2 > 0:
    ans = n-k+1-cnt-cnt2
else:
    ans = n-k+1-cnt
    

print(ans)

Submission status: Wrong Answer

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

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

if temp > K-1:
    same = 1
else:
    same = 0

ans, m, M = 1, min(P[:K]), max(P[:K])
for i in range(N-K):
    change = False
    if P[i] == m:
        m = min(P[i+1:i+K])
    else:
        change = True

    if P[i+K] >= M:
        M = P[i+K]
    else:
        change = True

    if P[i+K] > P[i+K-1]:
        temp += 1
        if temp == K - 1:
            same += 1
    else:
        temp = 0

    if change:
        ans += 1

if same > 0:
    ans -= same - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
num,div= input().split()
num = int(num)
div = int(div)
ar = np.array(list(map(int, input().split())))
box = [str(np.hstack((np.sort(ar[:div]),ar[div:]))),str(np.hstack((ar[:div],np.sort(ar[div:]))))]
for i in range(1,num-div):
  box.append(str(np.hstack((ar[:i],np.sort(ar[i:i+div]),ar[i+div:]))))
print(len(np.unique(box)))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # l=[i for i in range(1,2001)]
  # print(' '.join([str(x) for x in l]))
  n,k=LI()
  l=LI()

  ans=0
  a=l[:k]
  sort_a=a.sort()
  if a!=sort_a:
    ans+=1

  j=0
  for i in range(k,n):
    b=l[i]
    c=bisect.bisect_right(a,b)
    if c!=k:
      ans+=1
    a.insert(c,b)
    d=a.index(l[j])
    if d!=0:
      ans+=1
    a.pop(d)
    print(a,ans)
    j+=1

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
class BpTree:
	M1 = 2
	M2 = M1 * 2
	
	def __init__(self):
		self.root = BpTree.Node([BpTree.Leaf([])])
	
	def insert(self, v, x):
		result = self.root.insert(v, x)
		if result:
			self.root = BpTree.Node([self.root, result])
	
	def to_list(self):
		items = []
		if self.root:
			self.root.to_list(items)
		return items
	
	def check(self):
		if self.root.check(True):
			return True
		else:
			print("ERROR")
			self.root.print()
			exit()
	
	def print(self):
		if self.root:
			self.root.print()
	
	def remove(self, v):
		self.root.remove(v)
	
	def min(self):
		return self.root.min

	def max(self):
		return self.root.max

	class Node:
		def __init__(self, children):
			self.children = children
			self.prev = None
			self.next = None
			if children:
				self.min = children[0].min
				self.max = children[-1].max
			else:
				self.min = None
				self.max = None
		
		def calc_min(self):
			if self.children:
				return self.children[0].calc_min()
			else:
				return None
		
		def calc_max(self):
			if self.children:
				return self.children[-1].calc_max()
			else:
				return None
		
		def find_index(self, v):
			count = len(self.children) - 1
			index = 0
			while index < count:
				if v <= self.children[index].max:
					break
				index += 1
#			print([child.calc_max() for child in self.children], index, v)
			return index

		def insert(self, v, x):
#			print(">", self.min, v, self.max)
			if self.min == None or self.min > v:
				self.min = v
			if self.max == None or self.max < v:
				self.max = v
			index = self.find_index(v)
			result = self.children[index].insert(v, x)
			if result:
#				print("new: ", result.min, result.max)
				self.children.insert(index + 1, result)
				if len(self.children) >= BpTree.M2:
					new_children = self.children[BpTree.M1:]
					self.children = self.children[0:BpTree.M1]
					self.update_max()
					return BpTree.Node(new_children)
				else:
					return None
			else:
				return None
		
		def remove(self, v):
			count = len(self.children)
			for index in range(count):
				child = self.children[index]
				if child.min <= v <= child.max:
					result = child.remove(v)
					if result:
						if index == 0:
							self.update_min()
						if index == count - 1:
							self.update_max()
						if len(child.children) < BpTree.M1:
							if index < count - 1:
#								print("mm1")
								self.merge(index)
							elif index > 0:
#								print("mm2")
								self.merge(index - 1)
						return True
					else:
						return False
		
		def merge(self, index):
			child_l = self.children[index]
			child_r = self.children[index + 1]
			count_l = len(child_l.children)
			count_r = len(child_r.children)
			if count_l + count_r < BpTree.M2:
#				print("M1", count_l, count_r)
				for child in child_r.children:
					child_l.children.append(child)
				child_l.update_max()
				del self.children[index + 1]
#				return True
			else:
				if count_l < count_r:
#					print("M2")
					item = child_r.children.pop(0)
					child_l.children.append(item)
				else:
#					print("M3")
					item = child_l.children.pop()
					child_r.children.insert(0, item)
				child_l.update_max()
				child_r.update_min()
#				return False
		
		def update_min(self):
			self.min = self.children[0].min
			
		def update_max(self):
			self.max = self.children[-1].max
		
		def to_list(self, items):
			for child in self.children:
				child.to_list(items)
		
		def print(self, prefix = ""):
			new_prefix = prefix + "   "
			for i in range(len(self.children)):
				child = self.children[i]
				print(prefix, "+({})".format(child.min))
				child.print(new_prefix)
				print(prefix, "+({})".format(child.max))
				new_prefix = prefix + "   "
#				print(prefix, "+", self.values[i], sep="")
#				if i < self.count - 1:
#					print(prefix, "|", sep="")
#				else:
#					print(prefix, "+", sep="")
		
#		def get_values(self):
#			return [self.values[i] for i in range(self.count)]
		
		def check(self, is_top = False):
			count = len(self.children)
			if count > 0:
				if self.children[0].min != self.min or self.children[-1].max != self.max:
					print("E1")
					print(self.children[0].min, self.min, self.calc_min())
					print(self.children[-1].max, self.max, self.calc_max())
					return False
				if count >= BpTree.M2 or ((not is_top) and count < BpTree.M1):
					print("E2", count)
					return False
				for i in range(len(self.children)):
					child = self.children[i]
					if child.children and (child.min < self.min or child.max > self.max):
						print("E3")
						return False
					if child.check(is_top and i == 0) == False:
						return False
			return True
		
	class Leaf:
		def __init__(self, children):
			self.children = children
#			self.min = children[0][0]
#			self.max = children[-1][0]
			if children:
				self.min = children[0][0]
				self.max = children[-1][0]
			else:
				self.min = None
				self.max = None
		
		def calc_min(self):
			if self.children:
				return self.children[0][0]
			else:
				return None
		
		def calc_max(self):
			if self.children:
				return self.children[-1][0]
			else:
				return None

		def update_min(self):
			self.min = self.children[0][0]
			
		def update_max(self):
			self.max = self.children[-1][0]

		
#		def get_children(self):
#			return [self.children[i] for i in range(self.count)]

		def insert(self, v, x):
			if self.min == None or self.min > v:
				self.min = v
			if self.max == None or self.max < v:
				self.max = v
			count = len(self.children)
			index = 0
			while index < count:
				entry = self.children[index]
				value = entry[0]
				if v == value:
					entry[1] = x
					return None
				elif v < value:
					break
				index += 1
			
			self.children.insert(index, [v, x])
			
			if len(self.children) >= BpTree.M2:
				new_children = self.children[BpTree.M1:]
				self.children = self.children[:BpTree.M1]
				self.update_max()
				return BpTree.Leaf(new_children)
			else:
				return None
		
		def remove(self, v):
			count = len(self.children)
			for index in range(count):
				if self.children[index][0] == v:
					del self.children[index]
					if count > 1:
						if index == 0:
							self.update_min()
						if index == count - 1:
							self.update_max()
					else:
						self.min = None
						self.max = None
					return True
			return False
		
		def to_list(self, items):
			list(self.children)
		
		def print(self, prefix):
			for v, x in self.children:
				print(prefix, "+", v, ":", x, sep="")
		
		def check(self, is_only = False):
			count = len(self.children)
			if count > 0:
				if count >= BpTree.M2 or ((not is_only) and count < BpTree.M1):
					print("EL1", is_only, count)
					return False
				if self.calc_min() != self.min or self.calc_max() != self.max:
					print("EL2", self.min, self.children, self.max)
					return False
				for i in range(count):
					child = self.children[i]
					if child[0] < self.min or child[0] > self.max:
						print("EL3", self.min, self.children, self.max)
						return False
					if i > 0 and self.children[i - 1][0] >= child[0]:
						print("EL4")
			return True

N, K = map(int, input().strip().split())

p_list = list(map(int, input().strip().split()))

bptree = BpTree()


not_sorted = False
count = 0
prev_p = 0
for i in range(K):
	p = p_list[i]
	bptree.insert(p, 0)
	if prev_p < p:
		count += 1
	else:
		if count >= K:
			not_sorted = True
		count = 1
	prev_p = p

total = 1
for j in range(N - K):
	p_min = bptree.min()
	p_max = bptree.max()
	p_del = p_list[j]
	p_add = p_list[j + K]
	if prev_p < p_add:
		count += 1
	else:
		count = 1
	
	if p_del != p_min or p_max > p_add:
		if count >= K:
			if not_sorted == False:
				total += 1
				not_sorted = True
		else:
			total += 1
	
	prev_p = p
	
	bptree.remove(p_del)
	bptree.insert(p_add, 0)

print(total)