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: Runtime Error

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

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

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

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

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

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p

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

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

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

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





s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
before_sort = False
minw = MinSlideWindow 
maxw = MaxSlideWindow

before_sort_i = 0

for i in range(k - 2):
    minw.put(i)
    maxw.put(i)

for i in range(n - k + 1):

    maxw.put(i + k - 2)
    maxw.get(i-1)
    minw.put(i + k - 2)
    minw.get(i-1)

    
    if before_sort:
        if p[i + k - 1] < p[i + k - 2]:
            num += 1
            before_sort = False 
        else:
            before_sort_i += 1
        continue
    
    else:
        if before_sort_i + k <= i or i <= k:
            for j in range(k - 1):
                if p[i + j] > p[i + j +1]:
                    break
            else:
                if not ident:
                    ident = True
                    num += 1
                before_sort = True
                before_sort_i = i
                continue

            if i == 0:
                num += 1
                continue

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

print(num)

Submission status: Runtime Error

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])

for i in range(n - k + 1):
    if M == p[i - 1]:
      M = max(p[i:i + k - 2])
    if m == p[i - 1]:
      m = min(p[i:i + k - 2])
        
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue


    if p[i - 1] > m or p[i + k - 1] < M:
        num += 1
        break
    

print(num)

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
import heapq

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

ans = 0
Q_max = [-x for x in P[:K]]
Q_min = [x for x in P[:K]]
heapq.heapify(Q_min)
heapq.heapify(Q_max)
D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

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

for i in range(N - K + 1):
    if i == 0:
        ans += 1
        if oc == K - 1:
            ordered_twice = True
    else:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1
        if oc == K - 1:
            if not ordered_twice:
                ordered_twice = True
                if P[i - 1] > Q_min[0] or D[K - 1] < -Q_max[0]:
                    ans += 1
        else:
            if P[i - 1] > Q_min[0] or D[K - 1] < -Q_max[0]:
                ans += 1
        if P[i - 1] == Q_min[0]:
            heapq.heappop(Q_min)
        if P[i - 1] == -Q_max[0]:
            heapq.heappop(Q_max)
        if D[K - 1] >= -Q_max[0]:
            heapq.heappush(Q_max, -D[K - 1])
        if D[K - 1] <= Q_min[0]:
            heapq.heappush(Q_min, D[K - 1])

print(ans)

Submission status: Runtime Error

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = n - k

for i in range(k - 1):
    if p[i] > p[i + 1]:
        num += 1
        break

for i in range(n - k - 1):
    for j in range(k - 1):
        if p[i] > p[i + j + 1]:
            num -= 1
        elif p[i + k] < p[i + j + 1]







print(num)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
a=list(map(int, input().split()))
b=list(map(int, input().split()))

answer=a[0] - a[1]
for i in range(a[0]):
  c=b[i:i+a[1]+2]
  if min(c)==c[0] and max(c)==c[a[1]+1]:
    answer-=1
  if i+a[1]+2 > a[0]:
    break;

print(answer)

Submission status: Runtime Error

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]

num = 1

for i in range(k - 1):
  if p[i] > p[i + 1]:
    num += 1
    break   
for i in range(n - k):
  if p[i] > p[i + 1] or p[i + k] > p[i + k +1]:
    num += 1

print(num)

Submission status: Runtime Error

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]

num = 1

for i in range(k - 1):
  if p[i] > p[i + 1]:
    num += 1
    break   
for i in range(n - k):
  if p[i] > p[i + 1] or p[i + k] > p[i + k +1]:
    num += 1
  else:
print(num)

Submission status: Runtime Error

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]

num = 1

for i in range(k - 1):
  if p[i] > p[i + 1]:
    num += 1
    break
#print(num)    
for i in range(n - k):
  if p[i] > p[i + 1] or p[i + k] > p[i + k +1]:
    num += 1
   # print("y")
  else:
    #print("no")
print(num)

Submission status: Runtime Error

Solution code:
%%time
import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]
p_cumsum = p_isordered.cumsum()

ans = n - k + 1
no_change = False
if p_isordered[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
if p_isorder[:k-1].all():
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    if p_isorder[i+1:i+k].all():
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[i+j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Runtime Error

Solution code:
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        diff = ''
        ans = 0
        for i, v in enumerate(input().split()):


        print(max(1, ans))


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

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

ans = n - k + 1
no_change = False
for j in range(k-1):
    if p[j] > q[j+1]:
        break
else:
    no_change = True


for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    for j in range(1,k):
        if q[j] > q[j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

line1 = input().strip()
line2 = input().strip()

N, K = list(map(int, line1.split(' ')))
P = list(map(int, line2.split(' ')))

count = 0

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

if ordered[K - 1] == K:
    flg = True
    count = 1

sorted_target = []
for i in range(K):
    bisect.insort(sorted_target, P[i])

for i in range(K, N):
    if ordered[i] >= K:
        if not flg:
            count += 1
        flg = True

    if P[i] < sorted_target[-1] or P[i - K] != sorted_target[0]:
        count += 1

    sorted_target.remove(P[i - K])
    bisect.insort(sorted_target, P[i])

print(count)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
s=0
for i in range(n-k+1):
    if p[i]<=p[i+1]<=p[i+2]:
        s+=1
for j in range(n-k-2):
    if p[i]==min(p[i],p[i+1],p[i+2],p[i+3]) and p[i+3]==max(p[i],p[i+1],p[i+2],p[i+3]):
        s+=-1
print(s)

Submission status: Runtime Error

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

pre_num = -1
k_sorted = 0
last = 0
for i in range(n):
  if p[i] > pre_num:
    last += 1
    if last == k:
      k_sorted += 1
  else:
    last = 1
  pre_num = p[i]
if k_sorted > 0:
  k_sorted -= 1

min_max = 0
for i in range(n - k):
  part = p_list[i : i + k + 1]
  min_k = min(part)
  max_k = max(part)
  if min_k == part[0] and max_k == part[-1]:
    min_max += 1
    
print(n - k + 1 - k_sorted - min_max)

Submission status: Runtime Error

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

import heapq
heap_min = []
heap_max = []

cnt = 1

s_li = []

for i in range(4): 
    heapq.heappush(heap_min, P[i])
    heapq.heappush(heap_max, -1*P[i])


for i in range(N-K):
    heap_min.remove(P[i])
    heap_max.remove(-1*P[i])
    
    heapq.heappush(heap_min, P[i+K])
    heapq.heappush(heap_max, -P[i+K])

    
    mi = heapq.heappop(heap_min)
    heapq.heappush(heap_min,mi)
    
    ma = -1*heapq.heappop(heap_max)
    heapq.heappush(heap_max, -1*ma)
    
   # print(heap_min, mi, ma)
    
    if ma != P[i+K] or (l_ma != P[i] and l_mi != P[i]):
        cnt += 1

    l_ma, l_mi = ma, mi

    
print(cnt)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

from collections import deque

qm = deque()
qM = deque()
for i in range(k):
    if not qm or qm[-1] < a[i]:
        qm.append(a[i])
    if not qM or qM[-1] > a[i]:
        qM.append(a[i])


ans = 0
for i in range(k-1,n):
    if qm[0] != a[i-k] or qM[0] != a[i]: 
        ans += 1
    if not qm or qm[-1] < a[i]:
        qm.append(a[i])
    if not qM or qM[-1] > a[i]:
        qM.append(a[i])
    if qm and qm[0] == a[i-k]:
        qm.popleft()
    if qM and qm[0] == a[i-k]:
        qM.popleft()
    

print(ans)

Submission status: Runtime Error

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

import heapq
heap_min = []
heap_max = []

cnt = 1

s_li = []

for i in range(4): 
    heapq.heappush(heap_min, P[i])
    heapq.heappush(heap_max, -P[i])


for i in range(N-K):
    heap_min.remove(P[i])
    heap_max.remove(-P[i])
    
    heapq.heappush(heap_min, P[i+K])
    heapq.heappush(heap_max, -P[i+K])

    
    mi = heapq.heappop(heap_min)
    ma = heapq.heappop(heap_max)
    
    if ma != P[i+K] or (l_ma != P[i] and l_mi != P[i]):
        cnt += 1

    l_ma, l_mi = ma, mi


        
    
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
q = p[:]
def unique_rows(data):
	uniq = np.unique(data.view(data.dtype.descr * data.shape[1]))
	return uniq.view(data.dtype).reshape(-1, data.shape[1])

m = np.zeros((n-k+1,n))

for i in range(n-k+1):
	p = q[:]
	p[i:i+k] = sorted(p[i:i+k])
	m[i] = p

m = unique_rows(m)
    
print(m.shape[0])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n,k = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

from collections import deque

qm = deque()
qM = deque()
for i in range(k):
    if not qm or qm[-1] < a[i]:
        qm.append(a[i])
    if not qM or qM[-1] > a[i]:
        qM.append(a[i])


ans = 0
for i in range(k,n):
    if qm[0] != a[i-k] or qM[0] != a[i]: 
        ans += 1
    if not qm or qm[-1] < a[i]:
        qm.append(a[i])
    if not qM or qM[-1] > a[i]:
        qM.append(a[i])
    if qm and qm[0] == a[i-k]:
        qm.popleft()
    if qM and qm[0] == a[i-k]:
        qM.popleft()
    

print(ans)

Submission status: Runtime Error

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=1
 
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:
        m = min(P[i : i+K])
        M = max(P[i : i+K])
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
# import numpy as np

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

p_before = 200001
up = 0

mins = [0]*(n+1-k)
maxs = [0]*(n+1-k)

for i in range(n+1-k):
    temp = p_list[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify, _siftup

line1 = input().strip()
line2 = input().strip()

N, K = list(map(int, line1.split(' ')))
P = list(map(int, line2.split(' ')))

q = [P[i] for i in range(K)]
heapify(q)

max_val = max(P[0 : K])
count = 1

max_update = 0

for m in range(0, N - K):
    if P[m] == q[0] and P[m + K] > max_val:
        heappop(q)
        heappush(q, P[m + K])
        max_val = P[m + K]

    elif P[m] == q[0] and P[m + K] < max_val:
        heappop(q)
        heappush(q, P[m + K])
        count += 1

    elif P[m] != q[0]:
        count += 1
        for i in range(K):
            if P[m] == q[i]:
                q[i] = q[0]
                heappop(q)
                _siftup(q, i)
                break
        heappush(q, P[m + K])
        if P[m + K] > max_val:
            max_val = P[m + K]


ordered_block_num = 0
max_update = 0
for m in range(1, N):
    if P[m - 1] < P[m]:
        max_update += 1
    else:
        max_update = 0

    if max_update == K - 1:
        ordered_block_num += 1

if ordered_block_num >= 2:
    count = count - (ordered_block_num - 1)

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
q = p[:]
def unique_rows(data):
	uniq = np.unique(data.view(data.dtype.descr * data.shape[1]))
	return uniq.view(data.dtype).reshape(-1, data.shape[1])

m = np.zeros((n-k+1,n),'int64')

for i in range(n-k+1):
	p = q[:]
	p[i:i+k] = sorted(p[i:i+k])
	m[i] = p

m = unique_rows(m)
    
print(m.shape[0])

Submission status: Runtime Error

Solution code:
def insert(target_list, target):
  region = [0, len(target_list)-1]
  while region[0] < region[1]:
    i = (region[0] + region[1]) // 2
    if target_list[i] < target and target < target_list[i+1]:
      target_list.insert(i+1, target)
      return
    if target_list[i] > target:
      region[1] = (region[0] + region[1]) // 2
    if target_list[i+1] < target:
      region[0] = (region[0] + region[1]) // 2 + 1

  target_list.append(target)

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

res_set = set()

target = []
for i in range(N - K + 1):
  if i == 0:
    target = P[i:i+K]
    target.sort()
  else:
    target.remove(P[i-1])
    insert(target, P[i+K-1])
  new_list = P[:i] + target + P[i+K:]
  res_set.add(new_list)

#print(res_set)
print(len(res_set))

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = map(int, input().split())
p = [int(i) for i in input().split()]
q = p[:]
def unique_rows(data):
	uniq = np.unique(data.view(data.dtype.descr * data.shape[1]))
	return uniq.view(data.dtype).reshape(-1, data.shape[1])

m = np.zeros((n-k+1,n),'int64')

for i in range(n-k+1):
	p = q[:]
	p[i:i+k] = sorted(p[i:i+k])
	m[i] = p

print(m)    
m = unique_rows(m)
    
print(m.shape[0])

Submission status: Runtime Error

Solution code:
from copy import deepcopy
def insert_sort(arr,start):
    for i in range(start+1,start+3) :
        j = i - 1
        ele = arr[i]
        while arr[j] > ele and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ele
    return arr
n,k=map(int,input().split())
p=list(map(int,input().split()))
y= deepcopy(p)
m=[]


for r in range(n-k+1):
    m.append(insert_sort(y,r))
    y=deepcopy(p)

m=list(map(list, set(map(tuple, m))))
print(len(m))

Submission status: Runtime Error

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+1 : i+K+1])
        continue
    else:
        count+=1
print(count)

Submission status: Runtime Error

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

Solution code:
from copy import deepcopy
def insert_sort(arr,start):
    for i in range(start+1,start+3) :
        j = i - 1
        ele = arr[i]
        while arr[j] > ele and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ele
    return arr
n,k=map(int,input().split())
p=list(map(int,input().split()))
y= deepcopy(p)
m=[]


for r in range(n-k+1):
    m.append(insert_sort(y,r))
    y=deepcopy(p)

m=list(map(list, set(map(tuple, m))))
print(m)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

readline = sys.stdin.readline
N, K = map(int, readline().split())
P = list(map(int, readline().split()))
STmax = Segtree(P, 0, True, max)
STmin = Segtree(P, 10**9, True, min)
ans = N - K + 1
upper = [0]*(N-1)
for i in range(N-1):
    if P[i] > P[i+1]:
        upper[i] = 1
upper = list(accumulate(upper)) + [0]
cnt = 0
for i in range(N-K):
    if upper[i+K-2] == upper[i-1]:
        cnt += 1
    elif P[i+K] == STmax.query(i+1, i+K+1) and P[i] == STmin.query(i, i+K):
        ans -= 1
if upper[N-2] == upper[N-K-1]:
    cnt += 1
print(ans - max(0, cnt-1))

Submission status: Runtime Error

Solution code:
import bisect

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

A = set()
for i in range(0, N-K+1):
  if i == 0:
    PK = sorted(X[:K])
  else:
    PK.remove(X[i-1])
    bisect.insort(PK, X[i+K-1])
  X = P.copy()
  X[i:i+K] = PK
  A.add(tuple(X))
  
print(len(A))

Submission status: Runtime Error

Solution code:
import numpy as np

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

m = np.zeros((n-k+1,n),'int64')

for i in range(n-k+1):
	p[i:i+k] = sorted(p[i:i+k])
	m[i] = p

m = np.vstack({tuple(row) for row in m})
    
print(m.shape[0])

Submission status: Runtime Error

Solution code:
from copy import deepcopy
def bubble_sort(arr,start):
    change = True
    while change:
        change = False
        for i in range(start,start+2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr
n,k=map(int,input().split())
p=list(map(int,input().split()))
y= deepcopy(p)
m=[]

for x in range(n-k+1):
    m.append(bubble_sort(y,x))
    y=deepcopy(p)
    print(m)
m=list(map(list, set(map(tuple, m))))

print(len(m))

Submission status: Runtime Error

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()
	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: Runtime Error

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 0
flag = 0
for i in range(N - K + 1):
    tmp = P[i:i + K]
    if tmp != sorted(tmp):
        ans += 1
        flag += 1
        if i < N-3 and P[i] <= min(tmp) and P[i + K] >= max(tmp):
            ans -= 1
if flag != N - K + 1:
    ans += 1
print(str(ans))

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
P = [int(p) for p in input().split()]

L = [0 for i in range(N-1)]
temp = P[0]
for i in range(1,N):
    if temp > P[i]:
        L[i-1] = 1
    temp = P[i]
    
cnt = 0
for i in range(K-2, N-K+1):
    if L[i] == 1:
        chk = 0
        for j in range(1,K):
            if L[i+j] == L[i-j]:
                chk += 1
            else:
                break
        if chk == K-1:
            cnt += 1
            
zero = []
z = 0
for i in range(N-1):
    if L[i] == 0:
        z += 1
    else:
        zero.append(z)
        z = 0

cnt2 = 0
for i in range(len(zero)):
    if zero[i] >= K-1:
        cnt2 += zero[i]-K+2
        
print(N-K+1-cnt-cnt2)

Submission status: Runtime Error

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: Runtime Error

Solution code:
import numpy as np

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

sorted_list = []

for i in range(n - k):
    sorted_p = sorted(p[i:i+k])
    sorted_list.append(p[:i] + sorted_p + p[i+k:])

print(np.unique(sorted_list, axis=0).shape[0])

Submission status: Runtime Error

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

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
    _ = P[:i] + sorted(P[i : i+K]) + P[i+K : ]
    S.add(tuple(_))
print(len(S))

Submission status: Runtime Error

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

p_before = 200001
up = 0

mins = [0]*(n-k)
maxs = [0]*(n-k)

for i in range(n+1-k):
    temp = p[i:i+k]
    mins[i] = min(temp)
    maxs[i] = max(temp)

mins = mins[:-1]
maxs = maxs[1:]

origin = 0
not_origin = 0

for p in p_list[:k]:
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if p == p_list[k-1]:
        if up >= k-1:
            origin = 1
        else:
            not_origin = 1


for p,i in zip(p_list[k:], range(k,n)):
    if p_before < p:
        up += 1
    else:
        up=0
    p_before = p*1

    if up >= k-1:
        origin = 1
    else:
        if p_list[i-k] == mins[i-k]:
            if p_list[i] != maxs[i-k]:
                not_origin += 1
        else:
            not_origin += 1


print(origin + not_origin)

Submission status: Runtime Error

Solution code:
import numpy as np

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

sorted_list = []

for i in range(n - k + 1):
    sorted_p = sorted(p[i:i+k])
    sorted_list.append(p[:i] + sorted_p + p[i+k:])

print(np.unique(sorted_list, axis=0).shape[0])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
import numpy as np
s=np.zeros((n-k+1,n))
#s=[]
for i in range(n-k+1):
    s[i]=p[:i]+sorted(p[i:i+k])+p[i+k:]
    
for i in range(n-k+1):
    s[i]=tuple(s[i])
print(len(set(tuple(s))))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(K):
  print(sorted(p))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
P = list(map(int,input().split()))
t=time.time()
#S = set()
S=[]

for i in range(N-K+1):
    _ = P[:i] + sorted(P[i : i+K]) + P[i+K : ]
    if _ not in S:
        S.append(_)
    #S.add(tuple(_))
print(len(S))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
import numpy as np
s=np.zeros((n-k+1,n))
#s=[]
for i in range(n-k+1):
    s[i]=p[:i]+sorted(p[i:i+k])+p[i+k:]
    
for i in range(n):
    s[i]=tuple(s[i])
print(len(set(tuple(s))))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
import numpy as np
s=np.zeros((n-k+1,n))
#s=[]
for i in range(n-k+1):
    s[i]=tuple(p[:i]+sorted(p[i:i+k])+p[i+k:])
    
print(len(set(tuple(s))))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
import numpy as np
s=np.zeros((n-k+1,n))
#s=[]
for i in range(n-k+1):
    s[i]=p[:i]+sorted(p[i:i+k])+p[i+k:]
    
kosuu=1
for i in range(len(s)-1):
    if tuple(s[i])!=tuple(s[i+1]):
        kosuu+=1
print(kosuu)

Submission status: Runtime Error

Solution code:
import bisect

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

ans = 1
for i in range(1,N-K+1):
  S = P[i:i+K-1]
  S.sort()
  if bisect.bisect_left(S,P[i-1]) == 0 and bisect.bisect_right(S,P[i+K]) == K-1:
    continue
  ans += 1
print(ans)