CodeEff/ECCO huggingface dataset:
# Original solution
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    s = S()
    rgb = [None for _ in range(n)]
    rgb_acc = [None for _ in range(n)]
    rgb_st = {"R","G","B"}
    rgb_lst = ["R","G","B"]
    for i, char in enumerate(s):
        if char == "R":
            rgb[i] = [1,0,0]
        elif char == "G":
            rgb[i] = [0,1,0]
        else:
            rgb[i] = [0,0,1]
    
    rgb_acc[0] = rgb[0]
    for i in range(1, n):
        rgb_acc[i] = rgb_acc[i-1][:]
        index = 0 if s[i]=="R" else 1 if s[i]=="G" else 2
        rgb_acc[i][index] += 1
    
    ans = 0
    for i in range(n-2):
        for j in range(i+1,n-1):
           if s[i]!=s[j]:
                ex = rgb_st - {s[i], s[j]}
                ex = ex.pop()
                index = 0 if ex=="R" else 1 if ex=="G" else 2
                cnt = rgb_acc[n-1][index]-rgb_acc[j][index]
                if j+1 <= 2*j-i < n:
                    if s[2*j-i] == ex:
                        cnt -= 1
                ans += cnt

    print(ans)
main()

# Optimized solution
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    s = S()
    rgb = ["R","G","B"]
    rgb_st = set(rgb)
    rgb_acc = [[0]*n for _ in range(3)]
    index = rgb.index(s[0])
    rgb_acc[index][0] += 1
    ans = 0

    for i in range(1,n):
        for j in range(3):
            rgb_acc[j][i] = rgb_acc[j][i-1]
        index = rgb.index(s[i])
        rgb_acc[index][i] += 1
    
    for i in range(n-2):
        for j in range(i+1,n-1):
            if s[i] != s[j]:
                ex = (rgb_st-{s[i],s[j]}).pop()
                index = rgb.index(ex)
                cnt = rgb_acc[index][-1] - rgb_acc[index][j]
                if j<2*j-i<n:
                    if s[2*j-i] == ex:
                        cnt -= 1
                ans += cnt
    print(ans)
main()
# Original solution
n=int(eval(input()))
s=input().rstrip()
count=0

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if (j-i)!=(k-j):
                if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                    count+=1
print(count)

# Optimized solution
n=int(eval(input()))
s=input().rstrip()
r=s.count("R")
g=s.count("G")
b=s.count("B")
count=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j+j-i<n:
            if s[i]!=s[j] and s[i]!=s[j+j-i] and s[j]!=s[j+j-i]:
                count+=1
print((r*g*b-count))
# Original solution
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(eval(input()))
mii = lambda: list(map(int, input().split()))
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

colors = [
    [R, G, B],
    [R, B, G],
    [G, R, B],
    [G, B, R],
    [B, R, G],
    [B, G, R],
]

cand = []
for C1, C2, C3 in colors:
    for c1 in C1:
        for c2 in C2:
            if c1 > c2:
                continue
            for c3 in C3:
                if c2 > c3:
                    continue
                if c1 > c3:
                    continue
                cand.append((c1,c2,c3))

ans = 0
for c1, c2, c3 in cand:
    if c2 - c1 != c3 - c2:
        ans += 1

print(ans)

# Optimized solution
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(eval(input()))
mii = lambda: list(map(int, input().split()))
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

colors = [
    [R, G, B],
    [R, B, G],
    [G, R, B],
    [G, B, R],
    [B, R, G],
    [B, G, R],
]

ans = 0

for C1, C2, C3 in colors:
    for c1 in C1:
        for c2 in C2:
            if c1 > c2:
                continue
            for c3 in C3:
                if c2 > c3:
                    continue
                if c1 > c3:
                    continue
                if c2 - c1 != c3 - c2:
                    ans += 1

print(ans)
# Original solution
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(eval(input()))
mii = lambda: list(map(int, input().split()))
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

colors = [
    [R, G, B],
    [R, B, G],
    [G, R, B],
    [G, B, R],
    [B, R, G],
    [B, G, R],
]

ans = 0

for C1, C2, C3 in colors:
    for c1 in C1:
        for c2 in C2:
            if c1 > c2:
                continue
            ans += len([c3 for c3 in C3 if c3 > c2 and abs(c3-c2) != abs(c2-c1)])

print(ans)

# Optimized solution
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(eval(input()))
mii = lambda: list(map(int, input().split()))
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt * g_cnt * b_cnt

for i in range(N):
    for dist in range(N):
        j = i + dist
        k = j + dist
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1

print(ans)
# Original solution
from collections import Counter
s = input().rstrip()
L = len(s)
d = Counter(s)
print((L//2-d["p"]))

# Optimized solution
s = input().rstrip()
print((len(s)//2-s.count("p")))
# Original solution
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    s = sys.stdin.readline().rstrip()
    n = len(s)
    dp = [0] * (n+1)
    for i in range(n):
        for j in range(i,-1,-1):
            g = dp[j] - (1 if s[i] == 'p' else 0)
            if 0 < j <= (i+1)//2:
                p = dp[j-1] + (1 if s[i] == 'g' else 0)
            else:
                p = -INF
            dp[j] = max(g,p)
    print((dp[n//2]))

if __name__ == '__main__':
    main()

# Optimized solution
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    s = sys.stdin.readline().rstrip()
    n = len(s)
    ans = 0
    for i in range(n):
        if i % 2 == 0:
            if s[i] == 'p': ans -= 1
        else:
            if s[i] == 'g': ans += 1
    print(ans)

if __name__ == '__main__':
    main()
# Original solution
a = int(eval(input()))
b = list(map(int, input().split()))
c = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0}
d = 0
for i in b:
    if 1 <= i <= 399:
        c[0] += 1
    elif 400 <= i <= 799:
        c[1] += 1
    elif 800 <= i <= 1199:
        c[2] += 1
    elif 1200 <= i <= 1599:
        c[3] += 1
    elif 1600 <= i <= 1999:
        c[4] += 1
    elif 2000 <= i <= 2399:
        c[5] += 1
    elif 2400 <= i <= 2799:
        c[6] += 1
    elif 2800 <= i <= 3199:
        c[7] += 1
    else:
        d += 1
e = 0
for k, v in list(c.items()):
    if v != 0:
        e += 1
print((str(max(e, 1)) + " " + str(e + d)))


# Optimized solution
a = int(eval(input()))
b = list(map(int, input().split()))
c = {}
for i in b:
    if 1 <= i <= 399:
        c[0] = 1
    elif 400 <= i <= 799:
        c[1] = 1
    elif 800 <= i <= 1199:
        c[2] = 1
    elif 1200 <= i <= 1599:
        c[3] = 1
    elif 1600 <= i <= 1999:
        c[4] = 1
    elif 2000 <= i <= 2399:
        c[5] = 1
    elif 2400 <= i <= 2799:
        c[6] = 1
    elif 2800 <= i <= 3199:
        c[7] = 1
    else:
        if 8 not in c:
            c[8] = 1
        else:
            c[8] += 1
count = 0
se = 0
for k, v in list(c.items()):
    if k == 8:
        se = v
    else:
        count += 1
if se == 0:
    print(("{} {}".format(count, count)))
else:
    if count == 0:
        print(("{} {}".format(1, se)))
    else:
        print(("{} {}".format(count, count + se)))
# Original solution
def c_ColorfulLeaderboard(N, A):
    from collections import defaultdict
    color = defaultdict(int)
    other = 0  # レート3200以上の選手の数
    for a in A:
        if 1 <= a <= 399:
            color['gray'] += 1
        elif 400 <= a <= 799:
            color['brown'] += 1
        elif 800 <= a <= 1199:
            color['green'] += 1
        elif 1200 <= a <= 1599:
            color['skyblue'] += 1
        elif 1600 <= a <= 1999:
            color['blue'] += 1
        elif 2000 <= a <= 2399:
            color['yellow'] += 1
        elif 2400 <= a <= 2799:
            color['orange'] += 1
        elif 2800 <= a <= 3199:
            color['red'] += 1
        elif 3200 <= a:
            other += 1
    # => 2 2,3 5,1 1
    return '{} {}'.format(max(1, len(color)), len(color) + other)

N=int(eval(input()))
A=[int(i) for i in input().split()]
print((c_ColorfulLeaderboard(N, A)))

# Optimized solution
def c_colorful_leaderboard(N, A):
    from collections import defaultdict
    rating_list = defaultdict(int)
    rating_color = ['gray', 'brown', 'green',
                    'skyblue', 'blue', 'yellow', 'orange', 'red']  # AtCoderのレート色
    other = 0  # レート3200以上の選手の数
    for rating in A:
        r = rating // 400  # レート色は400刻みで変わるため
        if r >= 8:  # レート3200位上
            other += 1
        else:
            rating_list[rating_color[r]] += 1
    ans = '{} {}'.format(max(1, len(rating_list)), len(rating_list) + other)
    return ans

N=int(eval(input()))
A=[int(i) for i in input().split()]
print((c_colorful_leaderboard(N, A)))
# Original solution
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N, K = list(map(int, input().split()))
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    rmq = SegmentTree(P)
    rMq = SegmentTree(P, merge_func=max, default=-1)
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq.query(i, i+K+1) or P[i+K] != rMq.query(i, i+K+1):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import math


def main():
    N, K = list(map(int, input().split()))
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    ln = int(math.log(K, 2))
    dp1 = [[0] * N for _ in range(ln+1)]
    dp2 = [[0] * N for _ in range(ln+1)]
    dp1[0] = P
    dp2[0] = P
    for k in range(ln):
        for i in range(N-2**k):
            dp1[k+1][i] = min(dp1[k][i], dp1[k][i+2**k])
            dp2[k+1][i] = max(dp2[k][i], dp2[k][i+2**k])
    rmq = [float("inf")] * (N-K+1)
    rMq = [0] * (N-K+1)
    for i in range(N-K+1):
        idx = i
        for k in range(ln+1)[::-1]:
            if K & (2**k):
                rmq[i] = min(rmq[i], dp1[k][idx])
                rMq[i] = max(rMq[i], dp2[k][idx])
                idx += 2**k
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq[i] or P[i+K] < rMq[i]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
from collections import deque
N,K = list(map(int,input().split()))
P = list(map(int,input().split()))

s = [1]*N
r = 0
for l in range(N):
    r = max(l,r)
    while r < N-1:
        if P[r]<P[r+1]:
            r += 1
        else:
            break
    s[l] = r-l+1
    
q = deque([N]+P[:K-1])

ans = 0

for i in range(N-K+1):
    q.append(P[i+K-1])
    if min(q)!=P[i-1] or max(q)!=P[i+K-1]:
        if s[i]<K:
            ans += 1
    q.popleft()

if max(s) >= K:
    ans += 1

print(ans)

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

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data_m = [INF]*(2*N0)
data_M = [INF]*(2*N0)

def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i, P[i], data_m)
    update(i, -P[i], data_M)

s = [1]*N
r = 0
for l in range(N):
    r = max(l,r)
    while r < N-1:
        if P[r]<P[r+1]:
            r += 1
        else:
            break
    s[l] = r-l+1
    
ans = 0
if s[0]<K:
    ans += 1

for i in range(1,N-K+1):
    if query(i-1,i+K,data_m)!=P[i-1] or query(i-1,i+K,data_M)!=-P[i+K-1]:
        if s[i]<K:
            ans += 1

if max(s) >= K:
    ans += 1

print(ans)
# Original solution
# -*- coding:utf8 -*-

n,k = list(map(int, input().split()))
p = list(map(int, input().split()))
ans = 1
all = [p]
for i in range(n - k):
    c = p[:i] + sorted(p[i:i+k]) + p[i+k:]
    if c not in all:
        ans += 1
        all.append(c)
print(ans)

# Optimized solution
# -*- coding:utf8 -*-

n,k = list(map(int, input().split()))
p = list(map(int, input().split()))
all = set()
all.add(''.join(map(str,p)))
for i in range(n - k):
    c = p[:i] + sorted(p[i:i+k]) + p[i+k:]
    all.add(''.join(map(str,c)))
print((len(all)))
# Original solution
from sys import stdin
import bisect
from collections import deque

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

ans = 0
Q = [-x for x in P[:K]]
Q.sort()
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[-1] or Q[0] < -P[i + K - 1]:
                    ans += 1
            if -P[i - 1] == Q[-1]:
                Q.pop()
            bisect.insort_left(Q, -P[i + K - 1])
        else:
            if -P[i - 1] != Q[-1] or Q[0] < -P[i + K - 1]:
                ans += 1
            if -P[i - 1] == Q[-1]:
                Q.pop()
            bisect.insort_left(Q, -P[i + K - 1])

print(ans)

# Optimized solution
from sys import stdin
from collections import deque

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

ans = N - K + 1

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

Q = deque([])
Q_min = []
Q_max = []

for i in range(N):
    while len(Q) > 0 and P[Q[len(Q) - 1]] >= P[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_min.append(P[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

PP = [-x for x in P]
Q = deque([])

for i in range(N):
    while len(Q) > 0 and PP[Q[len(Q) - 1]] >= PP[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_max.append(-PP[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

for i in range(N - K + 1):
    if i > 0:
        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 (Q_min[i - 1] == P[i - 1] and Q_max[i] == D[-1]) or (oc == K - 1 and ordered_twice):
            ans -= 1

    if oc == K - 1:
        ordered_twice = True

print(ans)
# Original solution
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
  
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
p = (n - k) + 1
c = []
for i in range(p):
  b = a.copy()
  b[i: i+k] = sorted(set(b[i: i+k]))
  c.append(b)
  
d = get_unique_list(c)
#d = set(list(map(tuple, c)))
print((len(d)))

# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
p = (n - k) + 1
c = []
for i in range(p):
  b = a.copy()
  b[i: i+k] = sorted(set(b[i: i+k]))
  if b not in c:
    c.append(b)
print((len(c)))
# Original solution
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
class SegTree:
    def __init__(self,size):
        self.N=size
        self.v=[-1]*(2*self.N-1)
        self.w=[10**6]*(2*self.N-1)
    def update(self,i,x):
        i+=self.N-1
        self.v[i]=x
        self.w[i]=x
        while i>0:
            i=(i-1)//2
            self.v[i]=max(self.v[i*2+1],self.v[i*2+2])
            self.w[i]=min(self.w[i*2+1],self.w[i*2+2])
    def max(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return -1
        if a<=l and r<=b:
            return self.v[i]
        return max(self.max(a,b,i*2+1,l,(l+r)//2),self.max(a,b,i*2+2,(l+r)//2,r))
    def min(self,a,b,i=0,l=0,r=1e9):
        if r==1e9:
            r=self.N
        if r<=a or b<=l:
            return 10**6
        if a<=l and r<=b:
            return self.w[i]
        return min(self.min(a,b,i*2+1,l,(l+r)//2),self.min(a,b,i*2+2,(l+r)//2,r))
s=SegTree(2**18)
x,n=0,0
for i,p in enumerate(P):
    s.update(i,p)
    if P[i-1]<P[i]:
        x+=1
        if K-1<=i and x==K-1:
            n+=1
            x-=1
    else:
        x=0
r=1
n=max(0,n-1)
for i in range(N-K):
    m,M=s.min(i+1,K+i),s.max(i+1,K+i)
    if not (P[i]<m and M<P[K+i]):
        r+=1
print((max(1,r-n)))

# Optimized solution
N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
from collections import deque
smin,smax=deque(),deque()
x,r,r2=0,0,0
for i,p in enumerate(P):
    while len(smin)>0 and P[smin[-1]]>p:
        smin.pop()
    smin.append(i)
    if smin[0]<=i-K:
        smin.popleft()
    while len(smax)>0 and P[smax[-1]]<p:
        smax.pop()
    smax.append(i)
    if smax[0]<=i-K:
        smax.popleft()
    if i>0 and P[i-1]<P[i]:
        x=min(x+1,K-1)
    else:
        x=0
    if i==K-1 or (i>=K and not (P[i-K]<P[smin[0]] and smax[0]==i)):
        if x!=K-1:
            r+=1
        else:
            r2=1
print((r+1 if r2 else r))
# Original solution
from itertools import accumulate
from collections import deque

N, K, *P = list(map(int, open(0).read().split()))

mi = []
Q = deque()
for i, p in enumerate(P):
    while Q and P[Q[-1]] > p:
        Q.pop()
    Q.append(i)
    if Q[0] == i - K:
        Q.popleft()
    mi.append(Q[0])

ma = []
Q = deque()
for i, p in enumerate(P):
    while Q and P[Q[-1]] < p:
        Q.pop()
    Q.append(i)
    if Q[0] == i - K:
        Q.popleft()
    ma.append(Q[0])

mi = mi[K - 1:]
ma = ma[K - 1:]

B = [mi[i] != i or ma[i + 1] != i + K for i in range(N - K)]

A = [0] + list(accumulate(x < y for x, y in zip(P, P[1:])))
S = [y - x != K - 1 for x, y in zip(A, A[K - 1:])]

ans = 1 + sum(b for b, s in zip(B, S[1:]) if s)
if S[0] and not all(S):
    ans += 1
print(ans)


# Optimized solution
from itertools import accumulate
from collections import deque

N, K, *P = list(map(int, open(0).read().split()))

def slide(A, K, cmp=lambda a, b: a > b):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and cmp(A[Q[-1]], a):
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

mi = slide(P, K)
ma = slide(P, K, lambda a, b: a < b)

B = [mi != i or ma != i + K for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]

A = [0] + list(accumulate(x < y for x, y in zip(P, P[1:])))
S = [y - x != K - 1 for x, y in zip(A, A[K - 1:])]

ans = 1 + sum(b for b, s in zip(B, S[1:]) if s)
if S[0] and not all(S):
    ans += 1
print(ans)