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 = 0
i = 0
while i < n:
    lst = p[i:i+k+1]
    tmp = sorted(lst)
    if i + k >= n:
        break
    for j in range(k+1):
        if tmp[j] != lst[j]:
            ans += 1
    i += k
if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,K=map(int,input().split())
P=list(map(int,input().split()))
ans=1
B=sorted(P[:K])
for i in range(N-K):
    pre_min=B[0]
    pre_v,next_v=P[i],P[i+K]
    bisect.insort_left(B, next_v)
    B.pop(bisect.bisect_left(B, pre_v))
    max_v=B[-1]
    if pre_min!=pre_v or max_v!=next_v:
        ans+=1
p=-1
cnt=0
S=0
for x in P:
   if p<=x:cnt+=1
   else:
       cnt=1
   if cnt>=K:S+=1
   p=x
if S!=0:S-=1
print(ans-S)

Submission status: Wrong Answer

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


out={}
for n,p in enumerate(P):
    changed=None
    Q=copy.copy(P)
    if n<len(P)-2:
        s=sorted(Q[n:n+K])
        if n==0:
            changed=s+Q[n+K:]
            out["".join(map(str,changed))]=changed 
        elif n==len(P)-K:
            changed=Q[0:n]+s
            out["".join(map(str,changed))]=changed 
        else:
            changed=Q[:n]+s+Q[n+K:]
            out["".join(map(str,changed))]=changed

print(len(out))

Submission status: Wrong Answer

Solution code:
from collections import deque

def sliding_minima(a, k):
    dq = deque()
    l = r = 0
    ret = []
    for i, item in enumerate(a):
        while(dq and a[dq[-1]] >= a[i]):
            dq.pop()
        dq.append(i)
        if i < k - 1:
            continue
        if dq[0] == i - k:
            dq.popleft()
        ret.append(a[dq[0]])
    return ret

def sliding_maxima(a, k):
    dq = deque()
    l = r = 0
    ret = []
    for i, item in enumerate(a):
        while(dq and a[dq[-1]] <= a[i]):
            dq.pop()
        dq.append(i)
        if i < k - 1:
            continue
        if dq[0] == i - k:
            dq.popleft()
        ret.append(a[dq[0]])
    return ret

def is_increasing(a, k):
    increasing = [0] * len(a)
    for i, (a1, a2) in enumerate(zip(a, a[1:])):
        if a1 < a2:
            increasing[i+1] = 1
    ret = [0] * (len(a) - k + 1)
    val = sum(increasing[1:k])
    for i in range(len(a) - k):
        val += increasing[i + k]
        val -= increasing[i + 1]
        if val == k-1:
            ret[i+1] = 1
        else:
            ret[i+1] = 0
    return ret

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

minima = sliding_minima(a, k)
maxima = sliding_maxima(a, k)
increasing = is_increasing(a, k)

ans = n - k + 1
for l, r, minima, maxima, inc in zip(a, a[k:], minima[1:], maxima, increasing[1:]):
    if (l < minima and r > maxima) or inc:
        ans -= 1
if sum(increasing) > 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
from heapq import *

input = sys.stdin.readline

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

# minq = [0]*N
minq = copy.deepcopy(P)
maxq = copy.deepcopy(P)

i = 0
j = 1
k = 1
while i<=N-2:
	sec = [10000000, -1]
	while P[i]<P[k] and k-i<=K-1:
		if P[k]<sec[0]:
			sec = P[k], k
		k += 1
		if k>N-1: break

	if sec[1]==-1:
		i = j
		j += 1
		k += 1
		# print(minq,i,j,k,sec[1])
		continue
	else:
		minq[j:k] = [P[i]]*(k-j)
		# print(minq,i,j,k,sec[1])
	if k>N-1: break
	if sec[0]<P[k]:
		i = sec[1]
		j = k
	else:
		i = k
		k += 1
		j = k
		if k>N-1: break

i = 0
j = 1
k = 1
while i<=N-2:
	sec = [-10000000, -1]
	while P[i]>P[k] and k-i<=K-1:
		if P[k]>sec[0]:
			sec = P[k], k
		k += 1
		if k>N-1: break

	if sec[1]==-1:
		i = j
		j += 1
		k += 1
		# print(maxq,i,j,k,sec[1])
		continue
	else:
		maxq[j:k] = [P[i]]*(k-j)
		# print(maxq,i,j,k,sec[1])
	if k>N-1: break
	if sec[0]>P[k]:
		i = sec[1]
		j = k
	else:
		i = k
		k += 1
		j = k
		if k>N-1: break

# print(minq)
# print(maxq)

if N==K:
	ans = 1
else:
	ans = 1
	for i in range(K,N):
		last = P[i]
		pre = P[i-K]
		if pre!=minq[i-1] or last!=maxq[i]:
			ans += 1
			# print(i)

	count = 0
	i = 0
	while i<N-1:
		upnum = 0
		while P[i]<P[i+1]:
			upnum += 1
			i += 1
			if i==N-1: break
		if upnum>=K-1:
			count += 1
		i += 1

	ans = ans-max(count-1,0)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
 
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
exist_sorted = 0
for i in range(ope_count):
  target = p[i:i+k]
  for j in range(1, math.ceil(k/2)):
    if target[j -1] > target[j] or target[k-j-1] > target[k-j]:
      break
  else:
    ans -= 1
    exist_sorted = 1
    continue
  if i != (ope_count -1):
    next_one = p[i+k]
    if target[0] == min(target) and next_one > max(target):
      ans -= 1
 
print(ans + exist_sorted)

Submission status: Wrong Answer

Solution code:
import sys
import copy
from heapq import *

input = sys.stdin.readline

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

# minq = [0]*N
minq = copy.deepcopy(P)
maxq = copy.deepcopy(P)

i = 0
j = 1
k = 1
while i<=N-2:
	sec = [10000000, -1]
	while P[i]<P[k] and k-i<=K-1:
		if P[k]<sec[0]:
			sec = P[k], k
		k += 1
		if k>N-1: break

	if sec[1]==-1:
		i = j
		j += 1
		k += 1
		# print(minq,i,j,k,sec[1])
		continue
	else:
		minq[j:k] = [P[i]]*(k-j)
		# print(minq,i,j,k,sec[1])
	if k>N-1: break
	if sec[0]<P[k]:
		i = sec[1]
		j = k
	else:
		i = k
		k += 1
		j = k
		if k>N-1: break

i = 0
j = 1
k = 1
while i<=N-2:
	sec = [-10000000, -1]
	while P[i]>P[k] and k-i<=K-1:
		if P[k]>sec[0]:
			sec = P[k], k
		k += 1
		if k>N-1: break

	if sec[1]==-1:
		i = j
		j += 1
		k += 1
		# print(maxq,i,j,k,sec[1])
		continue
	else:
		maxq[j:k] = [P[i]]*(k-j)
		# print(maxq,i,j,k,sec[1])
	if k>N-1: break
	if sec[0]>P[k]:
		i = sec[1]
		j = k
	else:
		i = k
		k += 1
		j = k
		if k>N-1: break

# print(minq)
# print(maxq)

if N==K:
	ans = 1
else:
	ans = 1
	for i in range(K,N):
		last = P[i]
		pre = P[i-K]
		if pre!=minq[i-1] or last!=maxq[i]:
			ans += 1
			# print(i)

	count = 0
	i = 0
	while i<N-1:
		upnum = 0
		while P[i]<P[i+1]:
			upnum += 1
			i += 1
			if i==N-1: break

		count += max(0,upnum-(K-2))
		i += 1

	ans = ans-max(count-1,0)

print(ans)

Submission status: Wrong Answer

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[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)
print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = LI()
D = defaultdict(int)
min_l = [0] * n
max_l = [0] * n


for i in range(k):
    D[L[i]] += 1



min_l[0] = min(D)
max_l[0] = max(D)


ret = 0
a = 0
for i in range(n - 1):
    if L[i + 1] >= L[i]:
        ret += 1
    else:
        if ret >= k - 1:
            a += 1
        ret = 0

if ret >= (k - 1):
    a += 1



r = k
l = 0
while r < n:
    D[L[r]] += 1
    D[L[l]] -= 1
    if not D[L[l]]:
        D.pop(L[l])
    r += 1
    l += 1
    min_l[l] = min(D)
    max_l[l] = max(D)



cnt = 1
for i in range(n - k):
    if L[i] == min_l[i] and L[i + k] == max_l[i + k]:
        continue
    else:
        cnt += 1


if a >= 2:
    print(cnt - (a - 1))
else:
    print(cnt)

Submission status: Wrong Answer

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

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

ans = n - k + 1
no_change = False
if p_ordered[: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_ordered[i+1:i+k].all():
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)
print(0)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

inf = float('inf')


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

    def find(self, x):
        if self.v[x] < 0:  # (負)は根
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0


n, k = map(int, input().split())
p = tuple(int(x) for x in input().split())

uf = UnionFind(n)

# xoooox
# o区間の最大最小を変数に持ち、p[x]と比較する

minimum = inf
maximum = -1
for i in range(1, k):
    if p[i] < minimum:
        minimum = p[i]
    if maximum < p[i]:
        maximum = p[i]

for i in range(n - k):
    if maximum < p[i + k]:
        maximum = p[i + k]
        if p[i] < minimum:
            uf.unite(i, i + 1)
            # print(i, i + 1)

    if p[i + 1] == minimum:
        minimum = min(p[i + 2:i + 1 + k])

    # print(minimum, maximum)

v = None
for i in range(n - k + 1):
    # print(p[i:i + k], tuple(sorted(p[i:i + k])))
    if p[i:i + k] == tuple(sorted(p[i:i + k])):
        if v is None:
            v = i
        else:
            uf.unite(v, i)

ans = 0
for i in range(n - k + 1):
    if uf.root(i):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, K = map(int, input().split())
        ans = 0
        q = queue.Queue()
        tmp = 0
        for i, v in enumerate(input().split()):
            if int(v) != i:
                q.put(True)
                tmp += 1
            else:
                q.put(False)
            if i >= K:
                if tmp > 0:
                    ans += 1
                if q.get():
                    tmp -= 1

        print(max(1, ans))


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

Submission status: Wrong Answer

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()):
            if int(v) != i:
                continue
            else:
                continue


        print(max(1, ans))


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

Submission status: Wrong Answer

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()):
            int(v)

        print(max(1, ans))


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

Submission status: Wrong Answer

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()):
            continue

        print(max(1, ans))


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

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 = 0
for i in range(1,n-k+1):
    l = a[i-1]
    r = a[i+k-1]
    min_ = min_st.query(i-1, i-1+k)    
    max_ = max_st.query(i, i+k)
    if l == min_ and r == max_:
        ans += 1

tmp = 0
cnt = 1
tmp_ans = 0
for i in range(1, n-k+1):
    if a[i-1] < a[i]:
        cnt += 1
    else:
        cnt = 1
    if cnt >= k:
        tmp_ans += 1
ans += 1 - max(tmp_ans - 1, 0)

print(ans)

Submission status: Wrong Answer

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()):
            if int(v) != i:
                diff += '1'
            else:
                diff += '0'


        print(max(1, ans))


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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(0)
for i in range(1,n):
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  if i<k:
    continue
  else:
    A1.append(P[M1[0]])
M2.append(0)
for i in range(1,n):
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  if i<k:
    continue
  else:
    A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i]==P[i] and A2[i]==P[i+k]:
    continue
  else:
    ans+=1
print(ans)

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(1,n-k+1):
    ans += 1
    l = a[i-1]
    r = a[i+k-1]
    min_ = min_st.query(i-1, i-1+k)    
    max_ = max_st.query(i, i+k)
    if l == min_ and r == max_:
        ans -= 1

tmp = 0
cnt = 0
ans += 1
for i in range(n):
    if a[i] > tmp:
        cnt += 1
    else:
        cnt = 1
    tmp = a[i]
    if cnt == k:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

inf = float('inf')


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

    def find(self, x):
        if self.v[x] < 0:  # (負)は根
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

    def size(self, x):
        return -self.v[self.find(x)]


n, k = map(int, input().split())
p = tuple(int(x) for x in input().split())

uf = UnionFind(n)

# xoooox
# o区間の最大最小を変数に持ち、p[x]と比較する

minimum = inf
maximum = -1
for i in range(1, k):
    if p[i] < minimum:
        minimum = p[i]
    if maximum < p[i]:
        maximum = p[i]

for i in range(n - k):
    if maximum < p[i + k]:
        maximum = p[i + k]
        if p[i] < minimum:
            uf.unite(i, i + 1)
            # print(i, i + 1)

    if p[i + 1] == minimum:
        minimum = min(p[i + 2:i + 1 + k])

    # print(minimum, maximum)

same = 0
for i in range(n - k + 1):
    # print(p[i:i + k], tuple(sorted(p[i:i + k])))
    if p[i:i + k] == tuple(sorted(p[i:i + k])):
        same += 1

ans = 0
for i in range(n - k + 1):
    if uf.root(i):
        ans += 1

if same > 1:
    ans -= same - 1

print(ans)