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:
#!/usr/bin/env python3
#AGC38 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
p = LI()
ans = n - k + 1
tmp = p[0]
cnt = 1
lst = []
for i in range(1,n):
    if tmp < p[i]:
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1
    tmp = p[i]
lst.append(cnt)
f = defaultdict(lambda : 0)
m = len(lst)
for i in range(m):
    f[lst[i]] += 1
for i in range(m):
    if lst[i] == k-1:
        if i+1 < m:
            if lst[i+1] == k-1:
                ans -= k-2
    elif lst[i] == k and f[lst[i]] > 1:
        ans -= f[lst[i]]
        ans += 1
        f[lst[i]] = 0
    elif lst[i] > k and f[lst[i]] > 0:
        ans -= (lst[i] - k + 1)*f[lst[i]]
        ans += 1
        f[lst[i]] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
res = 1


for i in range(0, n - k):
    if i == 0:
        partp = p[0:k]
        sortpartp = np.sort(partp)
        if not ((partp == sortpartp).all()):
            res += 1
    else:
        rightp = p[i + k - 1]
        leftp = p[i - 1]
        partp = np.append(partp, rightp)
        partp = np.delete(partp, 0)

        if np.max(partp) == rightp:
            if np.min(partp) > leftp:
                pass
            else:
                sortpartp = np.sort(partp)
                if (partp == sortpartp).all():
                    pass
                else:
                    res += 1
print(res)

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
    tmp = P[idx:idx + K]
    if tmp[0] > left and tmp[-1] > right:
        ans -= 1
    left = tmp[0]
    right = tmp[-1]

print(ans)

Submission status: Wrong Answer

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

ans = 1

for i in range(n - 2):
    for j in range(i, i + 3):
        if a[i] > a[j]:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,K=map(int,input().split())
P=tuple(map(int,input().split()))
class SegTree:
    def __init__(self,size):
        self.N=size
        self.v=[-1]*(2*self.N-1)
        self.w=[10**6]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        self.w[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=max(self.v[i*2+1],self.v[i*2+2])
            self.w[i]=min(self.w[i*2+1],self.w[i*2+2])
    def val(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return -1,10**6
        if a<=l and r<=b:
            return self.v[i],self.w[i]
        M1,m1=self.val(a,b,i*2+1,l,(l+r)//2)
        M2,m2=self.val(a,b,i*2+2,(l+r)//2,r)
        return max(M1,M2),min(m1,m2)
s=SegTree(2**18)
x,n=0,0
for i,p in enumerate(P):
    s.update(i,p)
    if i>0 and P[i-1]<P[i]:
        x+=1
        if x==K-1:
            n+=1
            x-=1
    else:
        x=0
r=1
for i in range(N-K):
    M,m=s.val(i+1,K+i)
    if not (P[i]<m and M<P[K+i]):
        r+=1
print(max(1,r-max(0,n-1)))

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
p_list = list(map(int, input().split()))
initial_number = N-K+1
ini_sw = 0
fin_sw = 0
count_1 = 0
count_2 = 0
for i in range(initial_number):
    p_range = p_list[i:i+K]
    p_range_asc = sorted(p_range)
    if p_range[-1] == p_range_asc[-1]:
        fin_sw = 1
    else:
        fin_sw = 0
    if fin_sw == 1 and ini_sw == 1:
        count_1 += 1
    if p_range[0] == p_range_asc[0]:
        ini_sw = 1
    else:
        ini_sw = 0
    
    if p_range == p_range_asc:
        count_2 += 1
if count_2 >= 1:
    count_2 -=1
output = initial_number - (count_1 + count_2) 
print(output)

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:
            heappop(Max)
        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:
#l=list(map(int, input().split()))
n,k=map(int, input().split())
l=list(map(int, input().split()))

ans = 0

for i in range(n):
    kiten = l[i]
    le = 0
    if (n-i >= k):
        le = k
    else:
        le = n -i
    for j in range(1,le):
        if (kiten > l[i+j]):
            ans+=1
if (ans == 0):
    ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
b = list(map(int,input().split()))
n=0
count = 0
for i in range(a[0]-a[1]):
  cnt = 0
  flg = 0
  while b[i+cnt] > b[i+cnt+1] and cnt < a[1]:
    cnt += 1
  if cnt != a[1]-1:
    count += 1
if count == 0:
  count = 1
print(count)

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)
#print([G.find(i) for i in range(N-K+1)])
print(len(set([G.find(i) for i in range(N-K+1)])))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
array = list(map(int, input().split()))
 
sum = 1
tempmax = -1 
tempmin = -1
tempArray = []

for i in range(n-k):
	if i == n-k-1:
		break
	tempArray = array[i:i+k]
    
	if i == 0 or array[i-1] == tempmax:
		tempmax = max(tempArray)
    
	if i == 0 or array[i-1] == tempmin:
		tempmin = min(tempArray)
        
	if tempmax > array[i+k+1] or tempmin < array[i]:
		sum+=1
	elif tempmax < array[i+k+1]:
		tempmax = array[i+k+1]
	elif tempmin > array[i+k+1]:
		tempmin = array[i+k+1]

print(sum)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
if N == K:
    print(1)
    exit()
MIN = min(P[:K])
MAX = max(P[1:K+1])
ans = 1
idx = 0
while True:
    if P[0+idx] == MIN and  P[K+idx] == MAX:
        pass
    else:
        ans += 1
    idx += 1
    if K+idx == N:
        break
    MIN = min(P[idx:K+idx])
    MAX = max(P[idx+1:K+1+idx])
if P[-K:] == sorted(P[-K:]):
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
n,k = map(int,input().split())

p = input().split()


cnt = 1

for i in range(n-k):
  sub_p = p[i:i + k]

  heapq.heapify(sub_p)

  for j in range(k):
    max = heapq.heappop(sub_p)
    if max != p[i+j]:
      cnt += 1
      break

print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def isSorted(ls):
    for i in range(len(ls)-1):
        if ls[i]>=ls[i+1]:
            return 0
    return 1

minval = min(P[0:K-1])
maxval = max(P[0:K-1])

for i in range(N-K+1):
    if P[i] > maxval:
        maxval = P[i]
    elif P[i] < minval:
        minval = P[i]

    if isSorted(P[i:i+K])==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif (i!=0) and (P[i-1] < minval) and (P[i+K-1] > maxval):
        continue
    else:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = list(map(int,input().split()))
c_sum = [0]
cnt = 0
for i in range(1,n):
    if p[i] < p[i-1]:
        c_sum.append(c_sum[-1] + 1)
    else:
        c_sum.append(c_sum[-1])
for i in range(n-k):
    if c_sum[i + k] - c_sum[i] > 0:
        cnt += 1
print(cnt if cnt else 1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
class SegTree:
    def __init__(self,size):
        self.N=size
        self.v=[-1]*(2*self.N-1)
        self.w=[10**6]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        self.w[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=max(self.v[i*2+1],self.v[i*2+2])
            self.w[i]=min(self.w[i*2+1],self.w[i*2+2])
    def val(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return -1,10**6
        if a<=l and r<=b:
            return self.v[i],self.w[i]
        M1,m1=self.val(a,b,i*2+1,l,(l+r)//2)
        M2,m2=self.val(a,b,i*2+2,(l+r)//2,r)
        return max(M1,M2),min(m1,m2)
s=SegTree(2**18)
x,n=0,0
for i,p in enumerate(P):
    s.update(i,p)
    if P[i-1]<P[i]:
        x+=1
        if K-1<=i and x==K-1:
            n+=1
            x-=1
    else:
        x=0
r=1
for i in range(N-K):
    M,m=s.val(i+1,K+i)
    if not (P[i]<m and M<P[K+i]):
        r+=1
print(max(1,r-max(0,n-1)))

Submission status: Wrong Answer

Solution code:
n, k = (int(i) for i in input().split())
plist = [int(i) for i in input().split()] 

nothing=0
tt=min(plist[:k])
uu=max(plist[:k])
minimum=[tt, plist.index(tt)]
maximum=[uu, plist.index(uu)]

soswitch=0
if plist[:k]==sorted(plist[:k]):
    soswitch=1

koho=[]
shohi=-1
icchi=0

for i in range(n-k+1):
    hajime=i
    owari=i+k-1
    
    if plist[owari]<minimum[0]:
        minimum=[plist[owari], owari]
    if plist[owari]>maximum[0]:
        maximum=[plist[owari], owari]
    if minimum[1]==hajime-1:
        tt=min(plist[hajime:owari+1])
        minimum=[tt, plist.index(tt)]
    if maximum[1]==hajime-1:
        uu=max(plist[hajime:owari+1])
        maximum=[uu, plist.index(uu)]
    
    if soswitch==1 and maximum[1]==owari:
        soswitch=1
        nothing+=1
    
    elif minimum[1]==hajime: 
        if maximum[1]==owari:
            moto=plist[hajime:owari+1]
            now=sorted(moto)
            hajime2=0
            owari2=0
            for i in range(k):
                if moto[i]!=now[i]:
                    if hajime2==0:
                        hajime2=hajime+i
                    owari2=hajime+i
            if hajime2==0:
                nothing+=1
                soswitch=1
            else:
                soswitch=0
            
            if soswitch==0:
                iswitch=0
                basho=0
                nowgage=shohi+1
                while iswitch==0:
                    if nowgage>=len(koho):
                        iswitch=1
                    else:
                        if koho[nowgage][0]<hajime2:
                            nowgage+=1
                        elif koho[nowgage][0]==hajime2:
                            if koho[nowgage][1]==hajime2 and koho[nowgage][2]==owari2:
                                icchi+=1
                                iswitch=2
                            else:
                                iswitch=1
                            basho=nowgage
                        else:
                            iswitch=1
                if iswitch!=2:
                    koho.append([hajime2, hajime2, owari2, 0])
        
        else: #比較の必要なし
            moto=plist[hajime:owari+1]
            now=sorted(moto)
            hajime2=0
            owari2=0
            for i in range(k):
                if moto[i]!=now[i]:
                    if hajime2==0:
                        hajime2=hajime+i
                    owari2=hajime+i
            if hajime2==0:
                nothing+=1
                soswitch=1
            else:
                koho.append([hajime2, hajime2, owari2, 0])
                soswitch=0
    
    else: #以降更新の心配なし
        if maximum[1]==owari:
            """
            soswitch=0
            moto=plist[hajime:owari+1]
            now=sorted(moto)
            hajime2=0
            owari2=0
            for i in range(k):
                if moto[i]!=now[i]:
                    if hajime2==0:
                        hajime2=hajime+i
                    owari2=hajime+i
            if hajime2==0:
                nothing+=1
                soswitch=1
            else:
                soswitch=0
            
            iswitch=0
            basho=0
            nowgage=shohi+1
            """
            iswitch=0
            basho=0
            nowgage=shohi+1
            ookoho=[]
            
            while iswitch==0:
                if nowgage>=len(koho):
                    iswitch=1
                else:
                    if koho[nowgage][0]<hajime:
                        nowgage+=1
                    elif koho[nowgage][0]==hajime:
                        if koho[nowgage][1]==hajime:
                            ookoho.append(koho[nowgage][2])
                            iswitch=2
                        else:
                            iswitch=1
                        basho=nowgage
                    else:
                        iswitch=1
            if iswitch==2:
                moto=plist[hajime:owari+1]
                now=sorted(moto)
                hajime2=0
                owari2=0
                for i in range(k):
                    if moto[i]!=now[i]:
                        owari2=hajime+i
                if hajime2==0:
                    nothing+=1
                    soswitch=1
                else:
                    soswitch=0
                
                iswitch=0
                basho=0
                nowgage=shohi+1
                if owari2 in ookoho:
                    icchi+=1
            soswitch=0
        else:
            soswitch=0
            pass #マジで
    
    shoswitch=0
    while shoswitch==0:
        if shohi>=len(koho)-2:
            shoswitch=1
        else:
            if koho[shohi+1][0]<hajime:
                koho[shohi+1][3]=1
                shohi+=1
            else:
                shoswitch=1

#print(icchi, nothing)
print(n-k+1 - (icchi+max(0, nothing-1)))

Submission status: Wrong Answer

Solution code:
import heapq
import numpy as np
n, k = map(int, input().split())
p = np.array(list(map(int, input().split())))
count = 1
flag = 0
esc = 0
for i in range(1, n):
    if flag < k-1:
        if p[i-1] < p[i]:
            flag += 1
        else:
            flag = 0
    else:
        flag = 0
    if flag == k-1:
        esc += 1

if esc > 0:
    esc -= 1
    
sub_max = max(p[0:k])        
for i in range(1, n - k + 1):
    sub = p[i:i+k]
    sub_min = list(sub.copy())
    #heapq.heapify(sub_max)
    heapq.heapify(sub_min)
    #print(p[i+k-1])
    if sub_max > p[i+k-1]:
        count += 1
        continue
    else:
        sub_max = p[i+k-1]
    if sub_min[0] < p[i-1]:
        count += 1
        continue
print(count - esc)

Submission status: Wrong Answer

Solution code:
data1 = input().split(" ")
N = int(data1[0])
K = int(data1[1])
P_list = list(map(lambda x:int(x),input().split(" ")))
ans = []
same = -1
repeat_num = N - K + 1
for i in range(0, repeat_num):
  if sorted(P_list[i:i+K]) == P_list[i:i+K]:
    same += 1
  elif sorted(P_list[i:i+K])[1:K] == sorted(P_list[i+1:i+K+1])[0:K-1]:
  	repeat_num -= 1
  else:
    pass

print(repeat_num -same)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
raw = list(map(int,input().split()))
num = 2**(n-1).bit_length()
seg1 = [0]*2*num
seg2 = [n]*2*num

def build(raw):
    for i in range(n):
        seg1[i+num-1] = raw[i]
        seg2[i+num-1] = raw[i]
    for i in range(num-2,-1,-1):
        seg1[i] = max(seg1[2*i+1],seg1[2*i+2])
        seg2[i] = min(seg2[2*i+1],seg2[2*i+2])
    return True

build(raw)
cnt = n-k+1

def query(seg,ele,segf,p,q):
    if q <= p:
        return False
    p += num - 1
    q += num - 2
    res = ele
    while q-p > 1:
        if not p%2:
            res = segf(res,seg[p])
        if q%2:
            res = segf(res,seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = segf(res,seg[p])
    else:
        res = segf(res,seg[p],seg[q])
    return res

def check(i):
    #print(i,query(seg1,0,max,i,i+k+1),query(seg2,n+1,min,i,i+k+1))
    return query(seg1,0,max,i,i+k+1) == raw[i+k] and query(seg2,n+1,min,i,i+k+1) == raw[i]

t = [0]*n
f = -1
c = -1
for i in range(n):
    if raw[i] > c:
        f += 1
    else:
        f = 0
    c = raw[i]
    t[i] = f

for i in range(n-k):
    if t[i+k-1] - t[i] == k-1 or check(i):
        #print("y")
        cnt -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

n, k = map(int, input().split(' '))
p = [int(num) for num in input().split(' ')]

if n == k:
  print('1')
  sys.exit()

ope_count = n - k + 1
ans = ope_count
for i in range(ope_count):
  target = p[i:i+k]
  if i == (ope_count - 1):
    for i in range(1, k):
      if target[i -1] > target[i]:
        break
    else:
      ans -= 1
  else:
    next_one = p[i+k]
    if target[0] == min(target) and next_one > max(target):
      ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:

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

ans = n - k + 1

s = list(map(int, input().split()))

prevmax = max(s[0:k])
prevmin = min(s[0:k])
minf = False
maxf = False

for i in range(n - k):
    af = False
    bf = False
    if minf:
        prevmin = min(s[i:i + k])
    
    if s[i] == prevmin:
        af = True
        minf = True
    else:
        minf = False
    
    if s[i + k] > prevmax:
        bf = True
        prevmax = s[i + k]
    
    if af and bf:
        ans -= 1

b = []
prev = s[0]

c = 1
nc = -1

for i in s[1:]:
    if prev > i:
        c = 1
    else:
        c += 1
        if c >= k:
            nc += 1
    prev = i

if nc > 0:
    ans -= nc

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)

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:
        c += 1

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

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
l=list(map(int, input().split()))
print(n-k)

Submission status: Wrong Answer

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

ans_li = []
prev = []
for x in range(k):
    prev.append(-1)

ans = 0
for i in range(n):
    sort_p = p_li[i : i + k]
    sort_p.sort()
    if prev[1:k+1] != sort_p[0:k-1]:
        ans += 1
    if i + k == n :
        break
    prev = sort_p
print(ans)

Submission status: Wrong Answer

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

a = p[0:k]
count = 0
for i in range(k,n):
    if p[i]>= max(a) and min(a) == p[i-k]:
        count += 1
        
print(n-k+1-count)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
P =  list(map(int,input().split()))
if N==K:
  print(1);exit()
else:
  ans = N-K+1
  flag = 0
  for i in range(len(P)):
    if i+K < N-1:
      s = P[i:i+K]
      if min(s) == s[0] and max(s) < P[i+K]:
        ans -= 1
      elif s == sorted(s) and flag == 0:
        ans -= 1
        flag = 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right


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


if __name__ == "__main__":
    [n, k] = li()
    p_list = li()

    no_sort_pattern = 0
    temp_no_sort = 0
    for index, p in enumerate(p_list[0:n - 1]):
        if p < p_list[index + 1]:
            temp_no_sort = temp_no_sort + 1
            if temp_no_sort >= k - 1:
                no_sort_pattern = no_sort_pattern + 1
        else:
            temp_no_sort = 0

    sorted_p_list = p_list[:]
    sorted_p_list[0:k] = sorted(sorted_p_list[0:k])
    pattern = 1
    # print(p_list)
    # print(sorted_p_list)
    # print()
    for i in range(n - k):
        insert_idx = bisect_right(sorted_p_list[i + 1:i + k], sorted_p_list[i + k])
        # print(i, sorted_p_list[i] != p_list[i], sorted_p_list[i + 1:i + k], sorted_p_list[i + k])
        if sorted_p_list[i] != p_list[i] or insert_idx != k - 1:
            pattern = pattern + 1

            before_sorted = sorted_p_list[i:i + k]
            remove_idx = bisect_right(before_sorted, p_list[i])
            new_before_sorted = before_sorted[0:remove_idx - 1]
            new_before_sorted.extend(before_sorted[remove_idx:])

            insert_idx = bisect_right(new_before_sorted, p_list[i + k])
            new_before_sorted.insert(insert_idx, p_list[i + k])
            sorted_p_list[i + 1:i + k + 1] = new_before_sorted

            sorted_p_list[i] = p_list[i]

        # print(pattern, sorted_p_list)
        # print()
    # print()
    # print(no_sort_pattern)
    if no_sort_pattern >= 2:
        print(pattern - no_sort_pattern + 1)
    else:
        print(pattern)

# 昇順を行う範囲のパターンはN-K+1
# 前の結果 b0, b2, ..., bi-1, s1, s2, ..., sk, ai+k, ..., an-1
# があったたときに s1, s2, ..., sk, ai+k と pi, sort(s2, s3, ..., ai+k) が同じ場合はパターンは増えていない
# そうなるのは、s1==piかつmax(s1, s2, ..., ai+k)==ai+kのとき
# s1==piは速く計算できる
# sort(s2, s3, ..., sk) = s2, s3, ..., sk なので ２分探索の挿入を行い、挿入位置が最後になるのであれば
#  max(s1, s2, ..., ai+k)==ai+k　であり、新しい s1, s2, ..., sk は挿入後の列となる
# N log N + N logN

Submission status: Wrong Answer

Solution code:
n, k = [int(s) for s in input().split()]
nums = [int(s) for s in input().split()]
import random
point = []
for i in range(n-1):
  if nums[i] > nums[i + 1]:
    point.append(random.random())
  else:
    point.append(0)
box = []  
for i in range(n - k + 1):
  total = 0
  for j in range(k -1):
    total += point[i + j]
  if total not in box or total == 0:
    box.append(total)
print(len(box))

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

next_small = [N]*N
G = []
heapq.heapify(G)
heapq.heappush(G, (-P[0], 0))
for i in range(1, N):
	judge = 0
	while judge == 0 and len(G) > 0:
		num = heapq.heappop(G)
		if -num[0] < P[i]:
			heapq.heappush(G, num)
			judge = 1
		else:
			next_small[num[1]] = i
	heapq.heappush(G, (-P[i], i))

before_large = [-1]*N
G = []
heapq.heapify(G)
heapq.heappush(G, (P[N - 1], N - 1))
for i in range(N - 2, -1, -1):
	judge = 0
	while judge == 0 and len(G) > 0:
		num = heapq.heappop(G)
		if num[0] > P[i]:
			heapq.heappush(G, num)
			judge = 1
		else:
			before_large[num[1]] = i
	heapq.heappush(G, (P[i], i))

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

num = 0
zero = 0
for i in range(1, N - K):
	if inc[i + K - 1] >= K:
		zero += 1
	elif next_small[i - 1] >= i - 1 + K and before_large[i + K -1] <= i - 1:
		num += 1

print(N - K + 1 - num - zero)

Submission status: Wrong Answer

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

ans_lis=[]
ind=[]
for i in range(n-k+1):
    a=p[i:i+k]
    a.sort()
    if p[i:i+k] == a:
        continue
    else:
 
        if not p[:i]+a+p[i+k:] in ans_lis:
            ans_lis.append(p[:i]+a+p[i+k:])
print(len(ans_lis))

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()
	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:
n,k = map(int,input().split())

p = input()[::2]


cnt = 1

for i in range(n-k):
  sub_p = p[i:i + k]
  sub_p_dash = "".join(sorted(sub_p))
  if sub_p_dash != sub_p:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

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

ans=0
flag = 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
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
p = [int(i) for i in input().split()]

c_list = p[0:k]
c_list.sort()
c_list.pop(0)
p.pop(0)
#print(c_list,p)                                                               
roop = n-k
count = 1

for i in range(roop):
    list = p[i:k+i]
    list.sort()
#    print(c_list,list[0:k-1])                                                 
    if c_list != list[0:k-1]:
#        print(str(i) + '=' + str(c_list))                                     
        count += 1
    c_list = list[1:]

print(count)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
d=0
t=1
a=0
for i in range(K-1):
    if P[i]>P[i+1]:
        t=1
    else:
        t+=1
if t==K:
    d=1
    m=P[0]
    M=P[K-1]
else:
    m=P[0]
    M=P[K-1]
for i in range(K,N):
    if P[i]<P[i-1]:
        t=1
    else:
        t+=1
        if t>K:
            d=1
            continue        
    if P[i-K]==min(P[i-K:i]) and P[i]==max(P[i-K:i]):
        continue
    a+=1
print(a+d)