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:
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
  for v in range(a[1]):
    if b[i+v] > b[i+v+1]:
      flg = 1
  count += flg
if count == 0:
  count = 1
print(count)

Submission status: Wrong Answer

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

cnt = 1

if P[:K] != sorted(P[0:K]):
    cnt += 1
    
l_ma = max(P[:4])
l_mi = min(P[:4])

for i in range(N-K-1):
    A = P[i+1:i+1+K]
    ma, mi = max(A),min(A)
    
    if l_ma > P[i+K] or l_ma == P[i]:
        cnt += 1

    l_ma, l_mi = ma, mi
    
print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = [int(x) for x in input().split()]
L = [[-1, -1, -1] for _ in range(N)]
S = [[-1, -1, -1] for _ in range(N)]
M = [0] * N
for i, p in enumerate(P):
  M[p] = i
for i in range(N):
  p = N - 1 - i
  l = M[p]
  for j in range(max(l - K + 1, 0), l + 1):
    if L[j][0] < 0:
      L[j][0] = p
      if j == 0 or L[j - 1][0] != p:
        L[j][1] = j
      else:
        L[j][1] = L[j - 1][1]
    else:
      j = L[j][2]
  for j in range(l, max(l - K, -1), -1):
    if L[j][0] == p:
      if j == N - 1 or L[j + 1][0] != p:
        L[j][2] = j
      else:
        L[j][2] = L[j + 1][2]
    else:
      j = L[j][1]
  p = i
  s = M[i]
  for j in range(max(s - K + 1, 0), s + 1):
    if S[j][0] < 0:
      S[j][0] = p
      if j == 0 or S[j - 1][0] != p:
        S[j][1] = j
      else:
        S[j][1] = S[j - 1][1]
    else:
      j = S[j][2]
  for j in range(s, max(s - K, -1) , -1):
    if S[j][0] == p:
      if j == N - 1 or S[j + 1][0] != p:
        S[j][2] = j
      else:
        S[j][2] = S[j + 1][2]
    else:
      j = S[j][1]
cnt = N + 1 - K
for i in range(N - K):
  if S[i][0] == P[i] and L[i][0] < P[i + K]:
    cnt -= 1
unsort = -1
inc = 0
for i in range(N - 1):
  if P[i] < P[i + 1]:
    inc += 1
  else:
    inc = 0
  unsort += 1 if inc >= K - 1 else 0
unsort = max(unsort, 0)
print(cnt - unsort)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 0
flag = 0
for i in range(N - K + 1):
    if P[i:i + K] != sorted(P[i:i + K]):
        ans += 1
        flag += 1
    if i < N-3:
        if P[i] < P[i + 2] and P[i + 2] < P[i + 1] and P[i + 3] > P[i + 1]:
            ans -= 1
if flag != N - K + 1:
    ans += 1
print(str(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

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

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
inp = input().split()
n = int(inp[0])
k = int(inp[1])
ar = list(map(lambda x: int(x), input().split()))
ans = list()

total = 0
i = 0
while i <= n-k:
  o = ar[i:i+k]
  s = sorted(o)
  d = 0
  for j in range(0, k):
    if o[j] != s[j]:
      d += 1
  if d <= 2:
    ind = True
    for x in ans:
      if x == (ar[:i]+s+ar[i+k:]):
        ind = False
        break
    total += 1
    ans.append(ar[:i]+s+ar[i+k:])
  i += 1

print(total)

Submission status: Wrong Answer

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

ans_li = []
prev = []
for x in range(k):
    prev.append(-1)
#print(prev)
ans = 0
for i in range(n):
    buf = []
    buf = copy.deepcopy(p_li)
    sort_p = buf[i : i + k]
    sort_p.sort()
    #print(prev[1:k+1], sort_p[0:k-1])
    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 = [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]
        
L2 = []
for i in range(N-1-K+2):
    temp = []
    for j in range(i,K+i-1):
        temp += [L[j]]
    L2.append(temp)

zero = 0
cnt = 0
for i in range(len(L2)):
    j = 1
    c = 0
    if 1 not in L2[i]:
        zero += 1
    else:
        jud = 0
        for l in range(len(L2[i])):
            if L2[i][l] == 1:
                jud = 1
                break
        while j <= K-2 and i+j < len(L2) and jud == 0:
            temp = L2[i+j]
            temp.reverse()
            if L2[i] == temp:
                cnt += 1
            temp.reverse()
            j += 1
        
print(N-K+1-cnt-zero+1)

Submission status: Wrong Answer

Solution code:
class SparseTableMAX():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return max(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


class SparseTableMIN():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return min(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
      
n, k = map(int, input().split())
a = list(map(int, input().split()))
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)
ans = 1
for i in range(n):
    if i + k > n:
        continue
    l = a[i]
    r = a[i+k-1]
    l_max = max_st.query(i, i+k-1)
    r_min = min_st.query(i+1, i+k)
    if l > r_min or l_max < r:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #間違ってるところを区間に含む/この含んでいるのが違うなら、あれですよと
    N,K = MI()
    P = LI()
    wrongs=deque()
    including = deque()
    for i in range(N-1):
        if P[i]>P[i+1]:
            wrongs.append(i+0.5)
    including=deque()
    for w in deepcopy(wrongs):
        if w < K-1:
            including.append(wrongs.popleft())
        else:
            break
    ans = 1
    zero_experiense = not including
    #区間の最大より小さいものを新たに含む場合もだめですよと。
    incs = set()
    heap = []
    for i in range(K):
        heappush(heap,-P[i])
        incs.add(P[i])

    for left in range(1,N-K+1):
        incs.remove(P[left-1])
        while -heap[0] not in incs:
            heappop(heap)
        #メンバとheap最大は正しい最大になってる


        right=left+K-1
        update = False
        if including and including[0]<left:
            update = True
            including.popleft()
        if wrongs and wrongs[0]<right:
            update = True
            including.append(wrongs.popleft())


        if update:
            if not including:
                if zero_experiense:
                    incs.add(P[right])
                    heappush(heap,-P[i])
                    continue

                else:
                    zero_experiense=True
            ans += 1
        else:
            maxim = -heap[0]
            if maxim>P[right] and including:
                ans +=1
        incs.add(P[right])
        heappush(heap, -P[right])

    print(ans)
        



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt = 1

s_li = [P]


if P[:4] != sorted(P[0:K]):
    cnt += 1
    
l_ma = max(P[:4])
l_mi = min(P[:4])

for i in range(N-K-1):
    A = P[i+1:i+1+K]
    ma, mi = max(A),min(A)
    
    if l_ma > P[i+K] or l_ma == P[i]:
        cnt += 1

    l_ma, l_mi = ma, mi
    
print(cnt)

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 -= 1
    elif lst[i] == k and f[lst[i]] > 1:
        ans -= lst[i] - k + 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:
n, k = map(int, input().split())
a = list(map(int, input().split()))
p = (n - k) + 1
prev = []
for i in range(p):
  b = a.copy()
  b[i: i+k] = sorted(set(b[i: i+k]))
  if prev == []:
    c = 0
    prev = b
  elif prev != b:
    c += 1
    prev = b
print(c)

Submission status: Wrong Answer

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

def l2str(l):
    ret = ''
    for i in l:
        ret += str(i)
    return ret

tmp = []
cnt = 0
bef = 999999
for i in P:
    if i < bef:
        cnt += 1
    tmp.append(cnt)
    bef = i

seg = []
ans = set()
for idx, val in enumerate(tmp):
    if idx == N - K + 1:
        break
    seg = list(set(tmp[idx:idx + K]))
    ans.add(l2str(seg))

print(len(ans))

Submission status: Wrong Answer

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

count = 0
c = 0
for i in range(N-K):
    if P[i:i+K] == sorted(P[i:i+K]):
        c += 1
        continue
    comp_min = min(P[i+1:i+K])
    comp_max = max(P[i+1:i+K])
    if P[i] < comp_min and comp_max < P[i+K]:
        count += 1
# comp = min(P[N-K:N-1])
# if P[N-2-K] < comp:
#     count += 1

if P[-K:] == sorted(P[-K:]):
    c += 1
if c > 1:
    count += 1
print(N-K+1-count)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
*P,=map(int,input().split())
a=b=0;s=[0]
for i,j in zip(range(N),range(K,N)):
    a+=P[i]>min(P[i:j])or P[j]<max(P[i:j])
l=[i<j for i,j in zip(P,P[1:])]
for r in l:
    s.append(r+s[-1])
for i,j in zip(s,s[K-1:]):
    b+=j-i==K-1
print(1+a+(1-b)*(b>0))

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #間違ってるところを区間に含む/この含んでいるのが違うなら、あれですよと
    N,K = MI()
    P = LI()
    wrongs=deque()
    including = deque()
    for i in range(N-1):
        if P[i]>P[i+1]:
            wrongs.append(i+0.5)
    including=deque()
    for w in deepcopy(wrongs):
        if w < K-1:
            including.append(wrongs.popleft())
        else:
            break
    ans = 1
    zero_experiense = not including
    #区間の最大より小さいものを新たに含む場合もだめですよと。
    incs = set()
    heap = []
    for i in range(K):
        heappush(heap,-P[i])
        incs.add(P[i])

    for left in range(1,N-K+1):
        incs.remove(P[left-1])
        while -heap[0] not in incs:
            heappop(heap)
        #メンバとheap最大は正しい最大になってる


        right=left+K-1
        update = False
        if including and including[0]<left:
            update = True
            including.popleft()
        if wrongs and wrongs[0]<right:
            update = True
            including.append(wrongs.popleft())


        if update:
            if not including:
                if zero_experiense:
                    incs.add(P[right])
                    heappush(heap,-P[i])
                    continue

                else:
                    zero_experiense=True
            ans += 1
        else:
            maxim = -heap[0]
            if maxim>P[right]:
                ans +=1
        incs.add(P[right])
        heappush(heap, -P[right])

    print(ans)
        



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

class SegmentTree:
    def __init__(self,N,default):
        #演算の定義
        self.op = min
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        
    #a_kの値をxに更新
    def update(self,k,x):
        k += self.N0-1
        self.tree[k] = x
        while k >= 0:
            k = (k-1)//2
            self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2])

    #区間[l,r]へのクエリ
    def query(self,l,r):
        L = l + self.N0; R = r + self.N0 + 1 
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    #k番目の値を取得
    def get(self,k):
        return self.tree[k+self.N0-1]

class Max_SegmentTree:
    def __init__(self,N,default):
        #演算の定義
        self.op = max
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        
    #a_kの値をxに更新
    def update(self,k,x):
        k += self.N0-1
        self.tree[k] = x
        while k >= 0:
            k = (k-1)//2
            self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2])

    #区間[l,r]へのクエリ
    def query(self,l,r):
        L = l + self.N0; R = r + self.N0 + 1 
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    #k番目の値を取得
    def get(self,k):
        return self.tree[k+self.N0-1]

from bisect import bisect_left

N,K = II()
P = III()

seg = SegmentTree(N,0)
for i in range(N):
    seg.update(i,P[i])

kmin = [False]*N
for i in range(N-K+1):
    a = seg.query(i,i+K-1)
    if a==P[i]:
        kmin[i] = True

seg2 = Max_SegmentTree(N,0)
for i in range(N):
    seg2.update(i,P[i])

kmax = [False]*N
for i in range(K-1,N):
    a = seg2.query(i-K+1,i)
    if a==P[i]:
        kmax[i] = True

dp = [0]*N
dp[K-1] = 1
flag = True
bad_p = []
for i in range(K-1):
    if P[i]>P[i+1]:
        flag = False
for i in range(N-1):
    if P[i]>P[i+1]:
        bad_p.append(i)

for i in range(K,N):
    now_flag = False
    if kmax[i]:
        if kmin[i-K]:
            dp[i] = dp[i-1]
        else:
            l = bisect_left(bad_p,i-K+1)
            r = bisect_left(bad_p,i)
            if l==r:
                now_flag = True
            if flag and now_flag:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1]+1
    else:
        dp[i] = dp[i-1]+1

    if now_flag:
        flag = True

print(dp[N-1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
sortList = []
for i in range(N-K+1):
    tmpList = P[i:i+K]
    print(tmpList)
    tmpWholeList = P[:]
    tmpWholeList[i:i+K] = sorted(tmpList)
    sortList.append(''.join(map(str, tmpWholeList)))


setList = list(set(sortList))
print(len(setList))

Submission status: Wrong Answer

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

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

print(sum)

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):
  if flag:
    flag=False
    continue
  if min(P[i:i+K])==P[i] and max(P[i+1:i+K+1]) == P[i+K]:
    if i == N-K-1:
      flag=True
  ans += 1
print(ans)

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
  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
      else:
        flag = 0
        for j in range(K-1):
          if s[j]>s[j+1] :
            flag = 1
            break
        if flag == 0:
          ans -= 1
print(ans)

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
    #print(plist[hajime:owari+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)]
    
    #print(minimum, maximum)
    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:
                #koho.append([hajime2, hajime2, owari2, 0])
                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
        else:
            soswitch=0
            pass #マジで
    
    
    if shohi>=len(koho)-2:
        pass
    else:
        if koho[shohi+1][0]<hajime:
            koho[shohi+1][3]=1
            shohi+=1

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

Submission status: Wrong Answer

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

A = list(map(int,input().split()))
ans = n-k+1
for i in range(n-k):
  new = A[i:i+k+1]
  if min(new) == new[0] and max(new) == new[k]:
    ans -= 1
count = 0
for i in range(n-k+1):
  new = A[i:i+k]
  newnew = sorted(new)
  if new == newnew:
    count += 1
if count == 0:
  ans -= count
else:
  ans -= count -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
p = list(map(int, input().split()))
cnt = 1
preL = p[0]
# preR = p[K - 1]
prerange_min = min(p[0:0 + K])
# prerange_max = max(p[0:0 + K])
sortMatchCnt = 0
for i in range(1, N - K + 1):
#  print(p[i:i + K])
  range_min = min(p[i:i + K])
  range_max = max(p[i:i + K])
  l = p[i]
  r = p[i + K - 1]
  sortMatchFlg = p[i:i + K] == sorted(p[i:i + K])
  if sortMatchFlg:
    sortMatchCnt += 1                         
  if (preL == prerange_min and r == range_max) or sortMatchFlg:
    pass
  else:
    cnt += 1
  preL = l
  # preR = r
  prerange_min = range_min
  # prerange_max = range_max
if sortMatchCnt >= 1:
  print(cnt + 1)
else:
  print(cnt)

Submission status: Wrong Answer

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

ans=0

for i in range(N-K):
  if min(P[i:i+K])==P[i] and max(P[i+1:i+K+1]) == P[i+K]:
    if i == N-K-1:
      ans+=1
  else:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

for i in range(N-K):
    tmpList = P[i:i+K-1]
    tmpWholeList = P[:]
    tmpWholeList[i:i+K-1] = sorted(tmpList)
    sortList.append(''.join(map(str, tmpWholeList)))

setList = list(set(sortList))
print(len(setList))

Submission status: Wrong Answer

Solution code:
import heapq

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

ans = n - k + 1

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

maxhq = [-x for x in s[0:k]]
minhq = s[0:k]
heapq.heapify(maxhq)
heapq.heapify(minhq)




for i in range(n - k):
    a = heapq.heappop(minhq)
    b = heapq.heappop(maxhq)
    if s[i] == a and s[i + k] > b * (-1):
        ans -= 1
    heapq.heappush(minhq, s[i+k])
    heapq.heappush(maxhq, -s[i+k])

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:
import bisect
N,K = map(int,input().split(' '))
P = list(map(int,input().split(' ')))

def simple():
	s = set({})
	for i in range(N-K+1):
		Q = tuple(P[:i]+sorted(P[i:i+K])+P[i+K:])
		s.add(Q)
	return len(s)

ans = 0
mi = -1 
sp = sorted(P[:K])
if sp != P[:K]:
	ans += 1
else:
	ans += 1
	mi += 1

for i in range(1,N-K+1):
	f = False
	if sp[0] != P[i-1]:
		f = True
	if sp[-1] > P[i+K-1]:
		f = True
	sp.remove(P[i-1])
	bisect.insort(sp,P[i+K-1])
	if sp == P[i:K+i]:
		mi += 1
	ans += int(f)
	#print(f,sp)
	#print(P[:i]+sp+P[K+i:])

ans -= max(0,mi)
#print("TRUE",simple())
print(ans)

Submission status: Wrong Answer

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

ans=0

for i in range(N-K):
  if min(P[i:i+K])==P[i] and max(P[i+1:i+K+1]) == P[i+K]:
    ans += 0
  else:
    ans += 1
print(ans)

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
for i in range(n-k):
    imin = min(p[i:i+k])
    imax = max(p[i:i+k])
    if p[i] == imin and imax < p[i+k]:
      	pass
    elif p[i+1] == imin and imax < p[i+k]:
        irekawaranai += 1
    else:
        ans += 1
if irekawaranai > 0:
    ans += 1
print(ans)

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
  for i in range(len(P)):
    if i+K < N-1:
      s = P[i:i+K]
      r = sorted(s)
      if s == r:
        ans -= 1
      elif r[0] == s[0] and r[-1] < P[i+K]:
        ans -= 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')


def main():
	N,k=map(int,input().split())

	p=list(map(int,input().split()))
	q=[n*(-1) for n in p]
	cnt=1
	
	hh=heapq.heapify
	hp=heapq.heappop
	for i in range(N-k-1):
		
		hh(p[i:i+k])
		hh(q[i+1:i+k+1])
		if hp(p[i:i+k])==p[i] and hp(q[i+1:i+k+1])==q[i+k+1]:
			cnt+=0
		else:
			cnt+=1
	print(cnt)

if __name__=='__main__':
	main()

Submission status: Wrong Answer

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

for i in range(N-K):
    tmpList = P[i:i+K]
    tmpWholeList = P[:]
    tmpWholeList[i:i+K] = sorted(tmpList)
    sortList.append(''.join(map(str, tmpWholeList)))

setList = list(set(sortList))
print(len(setList))

Submission status: Wrong Answer

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

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

cnt = 1

for i in range(n-k):
  p_ = p[i:i +k]
  for j in range(k):
    if j != k-1:
      if p_[j] > p_[j+1]:
        cnt += 1
        break

print(cnt)