Problem: 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.

Submission attempts (in order):
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)

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)


s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
M = 0
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 + k -1] > p[i + k]:
        num += 1
    elif p[i] > p[i + 1]:
        for j in range(k-1):
            if p[i + j + 1] > p[i + j + 2]:
                num += 1
                break
            else:
                M = p[i + 1]
                for l in range(k - 1):
                    if M < p[i + l + 1]:
                        M = p[i + l + 1]
                        print(M)
                if M > p[i + k - 1]:
                    num += 1

print(num)

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)


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)

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 -1] > p[i + k]:
    num += 1

print(num)

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):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break

        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue
    else:
        if p[i - 1] > min(p[i:i + k - 1]) or p[i + k - 1] < max(p[i:i + k - 1]):
            num += 1      
    

print(num)


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 -1] > p[i + k]:
    num += 1

print(num)

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]:
      M = max(p[i + 1:i + k])
    if m == p[i]:
      m = min(p[i + 1: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
        continue

    if i == 0:
        num += 1
        continue

    for j in range(1,k):
        if p[i - 1] > M or m < p[i + j - 1]:
            num += 1
            break
    

print(num)


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)

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]:
      M = max(p[i:i + k])
    if m == p[i]:
      m = min(p[i: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
        continue

    if i == 0:
        num += 1
        continue

    for j in range(1,k):
        if p[i - 1] > M or m < p[i + j - 1]:
            num += 1
            break
    

print(num)


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]:
      M = max(p[i + 1:i + k])
    if m == p[i]:
      m = min(p[i + 1: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
        continue

    if i == 0:
        num += 1
        continue


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

print(num)


s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
M = 0
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 + k -1] > p[i + k]:
        num += 1
    elif p[i] > p[i + 1]:
        for j in range(k-1):
            if p[i + j + 1] > p[i + j + 2]:
                num += 1
                break
            else:
                M = p[i + 1]
                for l in range(k - 2):
                    if M < p[i + l + 1]:
                        M = p[i + l + 1]
                        print(M)
                if M > p[i + k - 1]:
                    num += 1

print(num)

s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
M = 0
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 + k -1] > p[i + k]:
        num += 1
    elif p[i] > p[i + 1]:
        for j in range(k-1):
            if p[i + j + 1] > p[i + j + 2]:
                num += 1
                break
            else:
                M = p[i + 1]
                for l in range(k - 2):
                    if M < p[i + l]:
                        M = p[i + l]
                if M > p[i + k - 1]:
                    num += 1

print(num)

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
so = False
M = max(p[:k])
m = min(p[:k])

print("{} {}".format(M,m))

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

            if not ident:
                ident = True
                num += 1
            so = True
            continue

        if i == 0:
            num += 1
            continue

        else:
            if M == p[i - 1] or M < p[i + k - 2]:
                M = max(p[i:i + k - 1])
            if m == p[i - 1] or m > p[i + k - 2]:
                m = min(p[i:i + k - 1])
    
            if p[i - 1] > m or p[i + k - 1] < M:
                num += 1       
    

print(num)



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

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

        while len(self.pos_list) > self.start_idx:
            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) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                self.start_idx += 1
            else:
                break

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

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0
        
    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            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) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                del self.pos_list[self.start_idx]
            else:
                break

    def max(self):
        pos1 = self.pos_list[self.start_idx]
        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 = 1
ident = True
rv_pos = -1

minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

for i in range(k - 1):
    if p[i] > p[i + 1]:
        rv_pos = i
        ident = False
    
for i in range(k-1):
    minw.put(i)
    maxw.put(i)

for i in range(1,n - k + 1):
    
    maxw.put(i + k - 2)
    minw.put(i + k - 2)
    maxw.get(i-1)
    minw.get(i-1)

    """    
    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 p[i + k - 2] > p[i + k - 1]:
        rv_pos = i + k - 2
        

    
    if rv_pos < i:
        if not ident:
            ident = True
            num += 1
        continue
            

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

    
print(num)


Verdicts: Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted