Harryxun/stf_run huggingface dataset:
# ABC164 D - Multiple of 2019
import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * 10**i % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1

ans_f = ans[np.nonzero(ans)]

print(int(sum([ans_f[i] * (ans_f[i]-1) for i in range(ans_f.shape[0])]) / 2) + ans[0])

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
s = input()
n, m = s.split()
n = int(n)
m = int(m)

maxd = m // (n - 1)

A = m - maxd * (n-1) + 1
B = m - (n-1) + 1
ans = (A+B)*maxd + (m+1)
ans %= 1000000007
print(ans)

### FIXED CODE ###

s = input()
n, m = s.split()
n = int(n)
m = int(m)

if n==1:
    print((m+1)%1000000007)
else:

    d = m // (n - 1)


    A = m - d * (n-1) + 1
    B = m - (n-1) + 1
    ans = (A+B)*d + (m+1)
    # ans = 2*(d*m+d)-(n-1)*(d+1)*d+m+1
    ans %= 1000000007
    print(ans)
p(long, raw_input().split())
max = max(n)
min = min(n)
sum = sum(n)
print "%d %d %d" %(min,max,sum)

### FIXED CODE ###

a = input()
n = map(long, raw_input().split())
max = max(n)
min = min(n)
sum = sum(n)
print "%d %d %d" %(min,max,sum)
def dp(n):# 頂点nから始まる最長経路を返す.
  if memo[n] != -1: return memo[n]
  to_list = Graph[n]
  answ = 0

  for i in to_list:
    answ = max(answ, dp(i)+1)
  memo[n] = answ
  return answ


N, M = map(int, input().split())
Graph = {n+1:[] for n in range(N)}
memo = [-1] * (N+1) # 各頂点からの最長経路をメモ. -1で初期化.

for _ in range(M):
  x, y = map(int, input().split())
  Graph[x].append(y)

ans = 0
for n in range(1,N+1):

  ans = max(ans, dp(n))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
MEMO = [-1 for _ in range(N+1)]

for _ in range(M):
  x, y = map(int, input().split())
  G[x].append(y)


def dp_LP(v):# 頂点nから始まる最長経路を返す.
  if MEMO[v] != -1:
    return MEMO[v]
  else:
    ans = 0
    for i in G[v]:
      ans = max(ans, dp_LP(i)+1)
    MEMO[v] = ans

    return ans



answer = 0
for n in range(1,N+1):
  answer = max(answer, dp_LP(n))
print(answer)
#n>=25なら鳩ノ巣で0
#2人以上居るdは一意
#あとはしらみつぶし

n = int(input())
if n>=25:
    print(0)
    exit()

d = list(map(int, input().split( )))
if 0 in d:##
    print(0)
    exit()
d.append(0)
dic = {}

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di]= 1
solo = []
times = []
for di in dic:
    if dic[di]==1:#di=0はここに入る
        solo.append(di)
    elif dic[di]==2:
        times.append(di)
        times.append(24-di)
    else:
        print(0)
        exit()
        
ans = 0
m = len(solo)
bit = 1<<m

for i in range(bit):
    times2 = []
    for t in times:
        times2.append(t)
    for j in range(m):
        if i>>j&1:
            times2.append(solo[j])
        elif solo[j]:
            times2.append(24-solo[j])
    times2.sort()
    dif = 24
    if len(times2)==1:###
        print(0)
        exit()
    #print(times2)

    for k in range(len(times2)-1):
        dif = min(dif,times2[k+1]-times2[k])
    dif = min(dif,times[0] + 24 - times[-1])
    ans = max(ans,dif)
print(ans)
 


### FIXED CODE ###

#n>=25なら鳩ノ巣で0
#2人以上居るdは一意
#あとはしらみつぶし

n = int(input())
if n>=25:
    print(0)
    exit()

d = list(map(int, input().split( )))
if 0 in d:##
    print(0)
    exit()
d.append(0)
dic = {}

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di]= 1
solo = []
times = []
for di in dic:
    if dic[di]==1:#di=0はここに入る
        solo.append(di)
    elif dic[di]==2:
        times.append(di)
        if di!=12:
            times.append(24-di)
        else:
            print(0)
            exit()
    else:
        print(0)
        exit()
        
ans = 0
m = len(solo)
bit = 1<<m

for i in range(bit):
    times2 = []
    for t in times:
        times2.append(t)
    for j in range(m):
        if i>>j&1:
            times2.append(solo[j])
        else:####???
            times2.append(24-solo[j])
    times2.sort()
    dif = 24
    if len(times2)==1:###
        print(0)
        exit()
    #print(times2)

    for k in range(len(times2)-1):
        dif = min(dif,times2[k+1]-times2[k])
    dif = min(dif,times2[0] + 24 - times2[-1])
    ans = max(ans,dif)
print(ans)
#!/usr/bin/env python3
# atcoder 
# Türkler var mı?
# Herkese memnün oldum
import sys

readline = sys.stdin.buffer.readline
iimr = lambda: map(int, sys.stdin.buffer.readline().rstrip().split())
#sys.setrecursionlimit(10 ** 8)

def debug(*x):
    print(*x, file=sys.stderr)


class atcoder():
    def __init__(self):
        pass

    def çözmek(self):
        N = int(input())
        A = list(map(int, sys.stdin.buffer.readline().split()))
        res = []
        res.append(self.関数(N, A))
        print(*res, "\n")	
    
    def 関数(self, n, Aliste):
        res = 0
        for i in range(1, n):
            if Aliste[i - 1] > Aliste[i]:
                res += Aliste[i - 1] - Aliste[i]
                Aliste[i] = Aliste[i - 1]

        return res

if __name__ == "__main__":
    ima = atcoder()
    ima.çözmek()



### FIXED CODE ###

#!/usr/bin/env python3
# atcoder 
# Türkler var mı?
# Herkese memnün oldum
import sys

readline = sys.stdin.buffer.readline

#iimr = lambda: map(int, sys.stdin.buffer.readline().rstrip().split())
# il ne y a pas plus le buffer sur atcoder
iimr = lambda: map(int, sys.stdin.readline().rstrip().split())
#sys.setrecursionlimit(10 ** 8)

def debug(*x):
    print(*x, file=sys.stderr)


class atcoder():
    def __init__(self):
        pass

    def çözmek(self):
        N = int(input())
        A = list(map(int, sys.stdin.readline().split()))
        res = []
        res.append(self.関数(N, A))
        print(*res, "")	
    
    def 関数(self, n, Aliste):
        res = 0
        for i in range(1, n):
            if Aliste[i - 1] > Aliste[i]:
                res += Aliste[i - 1] - Aliste[i]
                Aliste[i] = Aliste[i - 1]

        return res

if __name__ == "__main__":
    ima = atcoder()
    ima.çözmek()
S = map(int,input())

for i in range(4) :
	if S[i-1] == S[i] :
		print('Bad')
	break :
	else: 
		print('Good')

### FIXED CODE ###

S = input()
 
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3] :
	print('Bad')
else:
	print('Good')
n=int(input())
l=[]
L=[]
for _ in range(n):
  s=input()
  l.append(s)
import collections
c = collections.Counter(l)

for i in range(n):
  L.append(c.most_common()[i][0])
  if i!=n-1:
    if c.most_common()[i][1] != c.most_common()[i+1][1]:
      break
L.sort()
L=' '.join(L)
print(L)

### FIXED CODE ###

import collections
n = int(input())
s = []
for _ in range(n):
    s.append(input())

c = collections.Counter(s)
m = c.most_common()[0]

ans = []
for _c in c.items():
    if _c[1] == m[1]:
        ans.append(_c[0])

for v in sorted(ans):
    print(v)
n,A,B=map(int,input().split())
s=list(input())
cnt=0
cnt_b=0
for i in range(n):
	if s[i]=='a' and cnt<a+b:
		print('Yes')
		cnt+=1
	else:
		print('No')
	elif s[i]=='b' and cnt<A+B and cnt_b<=B:
			print('Yes')
		else:
			print('No')
	elif s[i]=='c':
		print('No')
		cnt_c+=1

### FIXED CODE ###

n,A,B=map(int,input().split())
s=list(input())
cnt=0
cnt_b=0
for i in range(n):
	if s[i]=='a' and cnt<A+B:
		print('Yes')
		cnt+=1
	elif s[i]=='b' and cnt<A+B and cnt_b<B:
		print('Yes')
		cnt_b+=1
		cnt+=1
	else:
		print('No')
from itertools import accumulate
S=list(map(len,input().split("T")))
x,y=map(int,input().split())
x=abs(x-S[0])
y=abs(y)
L=S[2::2]
R=S[1::2]
La=list(accumulate(L))
Ra=list(accumulate(R))
sumL=sum(L)
sumR=sum(R)
flag=0
if sumL>=x and sumR>=y and (sumL-x)%2==0 and (sumR-y)%2==0 and flag==0:
    setL1={0}
    setR1={0}
    gL=(sumL-x)//2
    gR=(sumR-y)//2
    if gL==0:
        flag=1
    else:
        for cnt,i in enumerate(L):
            setL=setL1
            setL1=set()
            s=setL1.add
            h=sumL-La[cnt]
            for j in setL:
                k=i+j
                #if k<gL and h+k>=gL:
                    s(k)
                #if j<gL and h+j>=gL:
                    s(j)
                elif k==gL:
                    flag=1
                    break
            if flag==1:
                break
    if flag==1:
        if gR==0:
            flag=2
        else:
            for cnt,i in enumerate(R):
                setR=setR1
                setR1=set()
                s=setR1.add
                h=sumR-Ra[cnt]
                for j in setR:
                    k=i+j
                    #if k<gR and h+k>=gR:
                        s(k)
                    #if j<gR and h+j>=gR:
                        s(j)
                    elif k==gR:
                        flag=2
                        break
                if flag==2:
                    break
if flag==2:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

from itertools import accumulate
S=list(map(len,input().split("T")))
x,y=map(int,input().split())
x=abs(x-S[0])
y=abs(y)
L=S[2::2]
R=S[1::2]
La=list(accumulate(L))
Ra=list(accumulate(R))
sumL=sum(L)
sumR=sum(R)
flag=0
if sumL>=x and sumR>=y and (sumL-x)%2==0 and (sumR-y)%2==0 and flag==0:
    setL1={0}
    setR1={0}
    gL=(sumL-x)//2
    gR=(sumR-y)//2
    if gL==0:
        flag=1
    else:
        for cnt,i in enumerate(L):
            setL=setL1
            setL1=set()
            s=setL1.add
            h=sumL-La[cnt]
            for j in setL:
                k=i+j
                #if k<gL and h+k>=gL:
                s(k)
                #if j<gL and h+j>=gL:
                s(j)
                if k==gL:
                    flag=1
                    break
            if flag==1:
                break
    if flag==1:
        if gR==0:
            flag=2
        else:
            for cnt,i in enumerate(R):
                setR=setR1
                setR1=set()
                s=setR1.add
                h=sumR-Ra[cnt]
                for j in setR:
                    k=i+j
                    #if k<gR and h+k>=gR:
                    s(k)
                    #if j<gR and h+j>=gR:
                    s(j)
                    if k==gR:
                        flag=2
                        break
                if flag==2:
                    break
if flag==2:
    print("Yes")
else:
    print("No")
n,x = map(int,input().split())
m = sorted([int(input()) for i in range(n)])
newx = x - sum(m)
c = n
 
for j in range(100):
  for i in m:
    newx -= i
    c +=1
    if newx < x - sum(m):
      break
if newx < x - sum(m):
  break
    
print(c-1)

### FIXED CODE ###

n,x = map(int,input().split())
m = sorted([int(input()) for i in range(n)])
newx = x - sum(m)
c = n
 
for i in range(114514):
  newx -= m[0]
  c += 1
  if newx < 0 :
    break

print(c-1)
n=int(input())
if n==22:
  print(Christmas Eve Eve Eve)
elif n==23:
  print(Christmas Eve Eve)
elif n==24:
  print(Christmas Eve)
else:
  print(Christmas)


### FIXED CODE ###

n=int(input())
if n==22:
  print('Christmas Eve Eve Eve')
elif n==23:
  print('Christmas Eve Eve')
elif n==24:
  print('Christmas Eve')
else:
  print('Christmas')
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
lis.sort(reverse=True)
while lis[-1]>10**5:
    lis.append(lis[-2]%lis[-1])
    n+=1
ex=[0 for i in range(lis[-1])]
for i in range(1,n):
    if ex[lis[i]%lis[-1]]==0:
        ex[lis[i]%lis[-1]]+=1
    if ex[lis[-1]-lis[i]%lis[-1]-1]==0:
        ex[lis[-1]-lis[i]%lis[-1]-1]+=1
#print(ex)
for i in range(n):
    if lis[i]<k:
        break
    elif lis[i]==k:
        print("POSSIBLE")
        sys.exit()
    elif ex[(lis[i]-k)%lis[-1]]==1:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")
    
    
    






        
        
    
    
        
    
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
lis.sort()
x=lis[0]
for i in range(n-1):
    x=gcd(x,lis[i+1])
if lis[-1]-k>=0 and (lis[-1]-k)%x==0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
def str_selection_sort(a,n):
    m=0
    for i in range(0,n):
        minj=i
        for j in range(i,n):
            if(int(a[minj][1:]) > int(a[j][1:])):
                minj=j
        if(minj!=i):
            m+=1
            a[minj],a[i] = a[i],a[minj]
        
    print(" ".join(a))
    return a

def bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    print(" ".join(a))

def is_stable(a,b,n):
    for i in range(1,n):
        if(b[i-1][1:]!=b[i][1:]):
            continue
        flag=False
        for j in a:
            if(j[:1]==b[i-1][:1] and (not flag)):
                flag=True
                continue
            if(j[:1]==b[i][:1]):
                if(not flag):
                    return False
                else:
                    return True
        
        if(flag):
            return False

a=[]
n=int(input())
s=input()
a=s.split()
b=str_bubble_sort(list(a),n)
if(is_stable(a,b,n)):
    print("Stable")
else:
    print("Not stable")
b=str_selection_sort(list(a),n)
if(is_stable(a,b,n)):
    print("Stable")
else:
    print("Not stable")

### FIXED CODE ###

def str_selection_sort(a,n):
    m=0
    for i in range(0,n):
        minj=i
        for j in range(i,n):
            if(int(a[minj][1:]) > int(a[j][1:])):
                minj=j
        if(minj!=i):
            m+=1
            a[minj],a[i] = a[i],a[minj]
        
    print(" ".join(a))
    return a

def str_bubble_sort(a,n):
    m=0
    flag=True
    while(flag):
        flag=False
        for i in range(n-1,0,-1):
            if(a[i-1][1:] > a[i][1:]):
                tmp=a[i-1]
                a[i-1]=a[i]
                m+=1
                a[i]=tmp
                flag=True
                
    print(" ".join(a))
    return a

def is_stable(a,b,n):
    for i in range(1,n):
        if(b[i-1][1:]!=b[i][1:]):
            continue
        flag=False
        for j in a:
            if(j[:1]==b[i-1][:1] and (not flag)):
                flag=True
                continue
            if(j[:1]==b[i][:1]):
                if(not flag):
                    return False
                else:
                    return True
        
        if(flag):
            return False
    return True

a=[]
n=int(input())
s=input()
a=s.split()
b=str_bubble_sort(list(a),n)
print("Stable")
c=str_selection_sort(list(a),n)
if(b==c):
    print("Stable")
else:
    print("Not stable")
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
for i in range(m):
    c,d = map(int,input().split())
    l = [0]*n
    for i in range(m):
        l[i] = abs(a[i][0]-c)+abs(a[i][1]-d)
    print(l.index(min(l))+1)

### FIXED CODE ###

n,m = map(int,input().split())
a,b = [[] for i in range(n)],[[] for i in range(n)]
c,d = [[] for i in range(m)],[[] for i in range(m)]
for i in range(n):
    a[i],b[i] = map(int,input().split())
for i in range(m):
    c[i],d[i] = map(int,input().split())

check = [[] for i in range(m)]
for i in range(n):
    for j in range(m):
        check[j] = abs(a[i]-c[j])+abs(b[i]-d[j])
    print(check.index(min(check))+1)
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y = self.root, None
        while x != None: x, y = x.left if key < x.key else x.right, x
        if y == None: self.root = Node(key)
        elif key < y.key: y.left = Node(key)
        else: y.right = z
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()


### FIXED CODE ###

import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(root)); print(preorder(root))
S = input()
K = input()
for i,n in enumerate(S):
  if n!= 1:
    break
print(n if i<K else 1)

### FIXED CODE ###

for i,n in enumerate(input()):
  if n!= '1':
    break
print(n if i<int(input()) else 1)
import math

if __name__ == '__main__':
	A, B = map(int, input().split())
	gcd = math.gcd(A,B)
	ans = (A//gcd) * B
	print(ans)

### FIXED CODE ###

import fractions as math

if __name__ == '__main__':
	A, B = map(int, input().split())
	gcd = math.gcd(A,B)
	ans = (A//gcd) * B
	print(ans)
# -*- coding: UTF-8 -*-
import math
# f=open("test.txt")
# line=f.readline()
# lists=[]
# while line:
#     lists.append("".join(list(line)[:-1]))
#     line=f.readline()
# 
# f.close()
# 
# s=lists[0]
# t=lists[1]

s=input()
t=input()

alpha=list("abcdefghijklmnopqrstuvwxyz")

dic_s={alpha[i]:0 for i in range(26)}
dic_t={alpha[i]:0 for i in range(26)}

a={alpha[i]:[] for i in range(26)}
b={alpha[i]:[] for i in range(26)}


for i in range(len(s)-1):
    if dic_s[s[i]]==0:
        dic_s[s[i]]=+1
        a[s[i]].append(i+1)


for j in range(len(t)-1):
    if dic_t[t[j]]==0:
        dic_t[t[j]]=+1
        b[t[j]].append(j+1)

flag=True

for i in range(26):
    if dic_t[alpha[i]]>0 and dic_s[alpha[i]]==0:
        flag=False

place=[0,0]

def binary(now,string):
    left=a[string][0]
    right=a[string][-1]
    #sのなかでstringがあり得る最大の位置
    #左のインデックスと右のインデックスを決める
    #now=現在いるindex
    flag=True
    if now>right:
        place[0]=left
        place[1]+=1

    elif now<left:
        place[0]=left
    else:
        indexl=0
        indexr=dic_s[string]-1
        for _ in range(20):
            c=math.floor((indexl+indexr)/2)
            if a[string][c]<=now:
                indexl=c
                indexr=indexr
            elif a[string][c]>now:
                indexl=indexl
                indexr=c
        place[0]=a[string][indexr]

if flag:
    #文字を構成できる場合
    for i in range(len(t)):
        string=t[i]
        now=place[0]
        binary(now,string)

    print(place[0]+place[1]*len(s))

else:
    #構成できない場合
    print(-1)


### FIXED CODE ###

# -*- coding: UTF-8 -*-
import math
import bisect
# f=open("test.txt")
# line=f.readline()
# lists=[]
# while line:
#     lists.append("".join(list(line)[:-1]))
#     line=f.readline()
# 
# f.close()
# 
# s=lists[0]
# t=lists[1]

s=input()
t=input()

alpha=list("abcdefghijklmnopqrstuvwxyz")

dic_s={alpha[i]:0 for i in range(26)}
dic_t={alpha[i]:0 for i in range(26)}

a={alpha[i]:[] for i in range(26)}
b={alpha[i]:[] for i in range(26)}


for i in range(len(s)):
  
    if dic_s[s[i]]==0:
        dic_s[s[i]]=+1
    a[s[i]].append(i+1)


for j in range(len(t)):
    
    if dic_t[t[j]]==0:
        dic_t[t[j]]=+1
    b[t[j]].append(j+1)
for i in range(26):
	a[alpha[i]].append(10**9)
flag=True

for i in range(26):
    if dic_t[alpha[i]]>0 and dic_s[alpha[i]]==0:
        flag=False

place=[0,0]

if flag:
    #文字を構成できる場合
    for i in range(len(t)):
        string=t[i]
        num=bisect.bisect_right(a[string],place[0])  
        if a[string][num]==10**9:
            place[1]+=1
            place[0]=a[string][0]
        else:
            place[0]=a[string][num]
  

    print(place[0]+place[1]*len(s))

else:
    #構成できない場合
    print(-1)
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    a[i - k + 1] = p[qa[0]]
    b[i - k + 1] = p[qb[0]]
ans = 1
for i in range(n - k - 1):
    if p[i] > a[i + 1] or b[i + 1] > p[i + k + 1] and l[i]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    if i >= k - 1:
        a[i - k + 1] = p[qa[0]]
        b[i - k + 1] = p[qb[0]]
ans = l[0]
for i in range(n - k - 1):
    if (p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]) and l[i + 1]:
        ans += 1
print(ans + 1 - min(l))