Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

ans = 0
ans_list = []
for i in range(N-K+1):
  exp = sum(p[i:i+K])
  if exp >= ans:
    ans = exp
    ans_list = p[i:i+K]
    
print((sum(ans_list)+K)/2)

### FIXED CODE ###

def cal(x): return (x+1)/2

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

ans  = sum(cal(p[i]) for i in range(K))
    
cnt = ans

for i in range(K, N):
  cnt = cnt-cal(p[i-K])+cal(p[i])
  ans = max(cnt, ans)
print(ans)
### BUGGY CODE ###

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

import itertools
lis = list(itertools.combinations(range(N), K))

mi = 0
for x in lis:
    cur = 0
    for pos in x:
        cur += p[pos]

    if mi == 0:
        mi = cur
    else:
        mi = min(mi, cur)

print(mi)

### FIXED CODE ###

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

sortp = sorted(p)

ans = 0
for x in range(K):
    ans += sortp[x]
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
for i in range(n):
    y = x[:]
    y.pop(i)
    y.sort()
    print(y[n//2-1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = x[:]
y.sort()
a = y[n//2-1]
b = y[n//2]
for i in x:
    if i <= a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    d = {}
    for i in A:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    r = 0
    for i in A:
        if d[i] == 0:
            continue
        for j in reversed(range(1,32)):
            t = pow(2, j) - i
            if t == i:
                if d[t] > 1:
                    d[t] -= 2
                    r += 1
            elif t in d and d[t] > 0:
                d[t] -= 1
                d[i] -= 1
                r += 1
    return r
print(main())


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    d = {}
    for i in A:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    r = 0
    for i in A:
        if d[i] == 0:
            continue
        for j in reversed(range(1,32)):
            t = pow(2, j) - i
            if t == i:
                if d[t] > 1:
                    d[t] -= 2
                    r += 1
            elif t in d and d[t] > 0:
                d[t] -= 1
                d[i] -= 1
                r += 1
    return r
print(main())
### BUGGY CODE ###

def com(n,r):
    if n-r<r:
        r=n-r
    re=1
    for i in range(n,n-r,-1):
        re*=i
    for i in range(1,r+1):
        re//=i
    return re

md=10**9+7
n,m,k=map(int,input().split())
ans=0
for d in range(1,m):
    ans=(ans+d*(m-d)*n*n)%md
for d in range(1,n):
    ans=(ans+d*(n-d)*m*m)%md
ans=(ans*com(n*m-2,k-2))%md
print(ans)


### FIXED CODE ###

def com(n,r):
    re=fct[n]*pow(fct[r],md-2,md)*pow(fct[n-r],md-2,md)
    re%=md
    return re

n,m,k=map(int,input().split())
md=10**9+7
ans=0
fct=[1]*(n*m-1)
f=1
for i in range(1,n*m-1):
    f=f*i%md
    fct[i]=f
for d in range(1,m):
    ans=(ans+d*(m-d)*n*n)%md
for d in range(1,n):
    ans=(ans+d*(n-d)*m*m)%md
ans=(ans*com(n*m-2,k-2))%md
print(ans)
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    toInt = {"R": 0, "G":1, "B": 2}
    count = [[0, 0, 0] for _ in range(N)]
    count[N-1][toInt[S[N-1]]] += 1
    for i in reversed(range(N-1)):
        for j in range(3): count[i][j] = count[i+1][j]
        count[i][toInt[S[i]]] += 1

    ans = 0
    for i in range(N-2):
        iInt = toInt[S[i]]
        for j in range(i+1, N-1):
            right = {0, 1, 2} - {iInt, toInt[S[j]]}
            if len(right) == 1:
                for key in right:
                    ans += count[j + 1][key]
                    if 2 * j - i < N and toInt[S[2*j - i]] == key: ans -= 1
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    col = {"R": 0, "G": 1, "B": 2}
    B = [[0, 0, 0] for _ in range(N)]
    B[N-1][col[S[N-1]]] = 1
    for i in reversed(range(N-1)):
        for j in range(3): B[i][j] = B[i+1][j]
        B[i][col[S[i]]] += 1

    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            if set((S[i], S[j])) == {"R", "G"}: 
                ans += B[j+1][2]
                if 2 * j - i < N and S[2 * j - i] == "B": ans -= 1
            elif set((S[i], S[j])) == {"B", "G"}: 
                ans += B[j+1][0]
                if 2 * j - i < N and S[2 * j - i] == "R": ans -= 1
            elif set((S[i], S[j])) == {"B", "R"}: 
                ans += B[j+1][1]
                if 2 * j - i < N and S[2 * j - i] == "G": ans -= 1
            
    print(ans)
            

    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n = int(input())
count = 0
ans = [i for i in range(1,n+1) if i%2==1]
def gcd(a,b):
    c = max(a,b)
    d = min(a,b)
    if b == 0:
        return a
    return gcd(b,a%b)

for i in ans:

    i_str = str(i)
    if i_str[0]=='3' or i_str[0]=='5' or i_str[0]=='7':
        three = i_str.count('3')
        five = i_str.count('5')
        seven = i_str.count('7')
        sum_number = three + five + seven
        if len(i_str) == sum_number and three>0 and five>0 and seven>0:
            count += 1

print(count)


### FIXED CODE ###

n = int(input())
ans = []
count = 0
def dfs(s):

    if int(s)>n:
        return 0
    ans.append(s)
    for c in '753':
        dfs(s+c)
dfs('0')
for i in ans:
    if all(i.count(j)>0 for j in '753'):
        count += 1
print(count)
### BUGGY CODE ###

import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint16)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                if n_cut >= ans:
                    break
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from bisect import bisect_left
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = [0, 0]
c = 0
for i in range(1, n):
    j = min(bisect_left(a, a[i]//2, 0, i), i-1)
    if a[i] <= a[j]:
        continue
    tmp = cmb(a[i], a[j])
    if tmp > c:
        ans[0], ans[1] = a[i], a[j]
        c = tmp
print(*ans)


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = [a[-1], 0]
m = float('inf')
for i in range(n-1):
    tmp = abs(ans[0]/2-a[i])
    if tmp < m:
        m = tmp
        ans[1] = a[i]

print(*ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(N):
    for j in range(N):
        if i+1 == a[j] and a[i] == j+1:
            ans += 1
            continue
print(int(ans/2))


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(N):
    if i+1 == a[a[i]-1]:
        ans += 1
        continue
print(ans // 2)
### BUGGY CODE ###

N, K = map(int,input().split())
monsters = list(map(int, input().split()))
monsters.sort(reverse=True)
count = 0

while K > count:
  count += 1
  try:
    monsters.pop(0)
  except IndexError:
    pass

print(sum(monsters))

### FIXED CODE ###

from collections import deque

N, K = map(int,input().split())
monsters = list(map(int, input().split()))
monsters.sort(reverse=True)
monsters = deque(monsters)
count = 0

while K > count:
  count += 1
  try:
    monsters.popleft()
  except IndexError:
    pass

print(sum(monsters))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
lr = list(list(map(int, input().split())) for _ in range(Q))

lst = [0] * N
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        lst[i] += 1

for i in range(Q):
    print( sum( lst[ lr[i][0] - 1 : lr[i][1] - 1 ] ) )


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
lr = list(list(map(int, input().split())) for _ in range(Q))

lst = [0] * N
'''
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        lst[i] += 1

for i in range(Q):
    print( sum( lst[ lr[i][0] - 1 : lr[i][1] - 1 ] ) )
'''
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C' and i == 0:
        lst[i] += 1
    elif S[i] == 'A' and S[i+1] == 'C':
        lst[i] += 1 + lst[i-1]
    else:
        lst[i] += lst[i-1]

for i in range(Q):
    print(lst[ lr[i][1] - 2 ] - lst[ lr[i][0] - 2 ] )
### BUGGY CODE ###

a,b,k = map(int, input().split())

for _ in range(k):
  if a>=1:
    a -= 1
  elif a==0:
    if b >= 1:
      b -= 1
  else:
    pass
  
print(a, b)

### FIXED CODE ###

a,b,k=map(int,input().split())
print(max(a-k,0),max(0,b-max(k-a,0)) )
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
py_dict = {}
cityi_by_year = []
for i in range(m):
  p, y = map(int, input().split())
  if p not in py_dict:py_dict[p] = [y]
  else:py_dict[p].insert(bisect.bisect_left(py_dict[p],y),y)
  cityi_by_year.append([p,y])
  
for p, y in cityi_by_year:
  idx = py_dict[p].index(y)
  print('0'*(6-len(str(p))) + str(p) + '0'*(6-len(str(idx+1))) + str(idx+1))


### FIXED CODE ###

import collections
import bisect
n,m=map(int,input().split())
p=[[int(j) for j in input().split()] for i in range(m)]
a=collections.defaultdict(list)
for x,y in sorted(p):
    a[x]+=[y]
for x,y in p:
    z=bisect.bisect(a[x],y)
    print("%06d%06d"%(x,z))
### BUGGY CODE ###

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n

t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    t = t * 10 % MOD

cnt = 0
for cr in range(n):
    cm = 0
    for cl in range(cr, n):
        cm = (cm + m[cl]) % MOD
        if cm == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

ans = 0
for i in range(MOD):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)
### BUGGY CODE ###

import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, m = ns()

    hm = [0 for _ in range(h)]
    wm = [0 for _ in range(w)]

    m_pos = {}

    for _ in range(m):
        hi, wi = ns()
        hi, wi = hi - 1, wi - 1
        hm[hi] += 1
        wm[wi] += 1

        if hi in m_pos.keys():
            m_pos[hi].add(wi)
        else:
            m_pos[hi] = {wi}

    h_max = []
    w_max = []

    tmax = -1
    for i, hi in enumerate(hm):
        if hi > tmax:
            tmax = hi
            h_max = [i]
        elif hi == tmax:
            h_max.append(i)

    tmax = -1
    for i, wi in enumerate(wm):
        if wi > tmax:
            tmax = wi
            w_max = [i]
        elif wi == tmax:
            w_max.append(i)

    ans = 0

    for hi in h_max:
        for wi in w_max:
            if wi in m_pos[hi]:
                ans = max(ans, hm[hi] + wm[wi] - 1)

            else:
                ans = max(ans, hm[hi] + wm[wi])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w, m = ns()

    hm = [0 for _ in range(h)]
    wm = [0 for _ in range(w)]

    m_pos = {}

    for _ in range(m):
        hi, wi = ns()
        hi, wi = hi - 1, wi - 1
        hm[hi] += 1
        wm[wi] += 1

        if hi in m_pos.keys():
            m_pos[hi].add(wi)
        else:
            m_pos[hi] = {wi}

    h_max = []
    w_max = []

    tmax = -1
    for i, hi in enumerate(hm):
        if hi > tmax:
            tmax = hi
            h_max = [i]
        elif hi == tmax:
            h_max.append(i)

    tmax = -1
    for i, wi in enumerate(wm):
        if wi > tmax:
            tmax = wi
            w_max = [i]
        elif wi == tmax:
            w_max.append(i)

    ans = 0
    breakflg = False

    for hi in h_max:
        for wi in w_max:
            if wi in m_pos[hi]:
                ans = max(ans, hm[hi] + wm[wi] - 1)
            else:
                ans = max(ans, hm[hi] + wm[wi])
                breakflg = True
                break
        if breakflg:
            break

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import fractions

N = int(input())
alist = list(map(int,input().split()))

max_gcd = 1
for skip in range(N):
  first = True
  for i,an in enumerate(alist):
    if i == skip:
      continue
    elif first:
      gcd = an
      first = False
      
    gcd = fractions.gcd(gcd,an)
    if gcd < max_gcd:
      break
    
  if max_gcd < gcd:
    max_gcd = gcd
    
print(max_gcd)

### FIXED CODE ###

import fractions

N = int(input())
alist = list(map(int,input().split()))

gcd_left_list = [0]*N
gcd = alist[0]
for i in range(1,N):
  gcd = fractions.gcd(gcd,alist[i-1])
  gcd_left_list[i] = gcd

gcd_right_list = [0]*N
gcd = alist[N-1]
for i in reversed(range(0,N-1)):
  gcd = fractions.gcd(gcd,alist[i+1])
  gcd_right_list[i] = gcd

#print(alist)
#print(gcd_left_list)
#print(gcd_right_list)
    
max_gcd = max(gcd_right_list[0], gcd_left_list[N-1])
for i in range(1,N-1):
  gcd = fractions.gcd(gcd_left_list[i],gcd_right_list[i])
  if gcd > max_gcd:
    max_gcd = gcd

print(max_gcd)
### BUGGY CODE ###

# 毎回やってもたかがしれてそう 包除原理
q = int(input())


def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(x ** 0.5) + 1):
        # print("{}%{}".format(x, i))
        if x % i == 0:
            return False
    return True


for _ in range(q):
    l, r = map(int, input().split())
    if l % 2 == 0:
        l += 1
    count = 0
    for x in range(l, r + 1, 2):
        # print("x={}".format(x))
        if isPrime(x) and isPrime((x + 1) // 2):
            count += 1
    print(count)


### FIXED CODE ###

# 毎回やってもたかがしれてそう -> 間に合いませんでした
# 素直に累積和+包除原理を使う

arr = [0 for _ in range(10 ** 5 + 1)]


def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True


for i in range(3, 10**5+1):
    if isPrime(i) and isPrime(int((i + 1) / 2)):
        arr[i] = 1
    arr[i] += arr[i-1]

q = int(input())


for _ in range(q):
    l, r = map(int, input().split())
    print(arr[r] - arr[l-1])
### BUGGY CODE ###

N = int(input())


def p_f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


hoge = p_f(N)

DP = [1]

if len(hoge) == 1:
    print(hoge[0]-1)
else:
    Min = 10**12

    for i in range(len(hoge)):
        for j in range(len(DP)):
            
            DP.append(DP[j]*hoge[i])

    for i in range(len(DP)):
        if (DP[i] + (N//DP[i]) - 2) < Min:
            Min = (DP[i] + (N//DP[i]) - 2)
            
    print(Min)

### FIXED CODE ###

N = int(input())


def make_divisors(n):  # 任意の整数の約数をリストで返す関数
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort()
    return divisors


List = make_divisors(N)

if len(List) % 2 == 1:
    print(List[len(List) // 2] * 2 - 2)
else:
    print(List[len(List) // 2 - 1] + (List[len(List) // 2] - 2))
### BUGGY CODE ###

import math
k = int(input())
v = 0
for a in range(1, k + 1):
  for b in range(1, k + 1):
    for c in range(1, k + 1):
      v += math.gcd(math.gcd(a, b), c)
print(v)


### FIXED CODE ###

import math
k = int(input())
v = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        g = math.gcd(a, b)
        for c in range(1, k + 1):
            v += math.gcd(g, c)
print(v)
### BUGGY CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))


    #残りk回のとき深さk以下の場所に正の宝石がない→終了
    #i回の操作で取れる石>それまでにとるi-1個の石の和
    #深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
    '''
    '''




    def tansaku(left,right,rK,N,score):
        dbg(V[left:right+1],rK,N,score)


        max_v = score + sum(sorted(N)[rK:])


        # n = []
        for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue

            #next_V = V[i+1:left+lenV]
            next_rK = rK - 1 - (i - left)
            next_tmp_v = tansaku(i+1,right,  next_rK, N+V[left:i], score+V[i])
            max_v = max(next_tmp_v , max_v)


            break

        # n = []
        for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
            
            if V[i] <= 0:
                #n.append(V[i])
                continue

            #next_V = V[:i]
            next_rK = rK - 1 - (right - i)
            #next_tmp_v = tansaku(   left,   i- left -1  ,next_rK,N+n,score+V[i])
            next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+V[i+1:right+1],score+V[i])
            max_v = max(next_tmp_v , max_v)
            break


        return max_v

    print(tansaku(0,len(V)-1,K,[],0))





if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = input()

r = [i for i in range(0, n) if s[i] == 'R']
g = [i for i in range(0, n) if s[i] == 'G']
b = [i for i in range(0, n) if s[i] == 'B']

cnt = 0
for elem1 in r:
    for elem2 in g:
        for elem3 in b:
            lst = sorted([elem1, elem2, elem3])
            if (lst[1] - lst[0]) != (lst[2] - lst[1]):
                cnt += 1
print(cnt)

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    r=[]
    g=[]
    b=[]
    rdict={}
    gdict={}
    bdict={}
    ans=0
    for i in range(n):
        if s[i]=='R':
            r.append(i)
            rdict[2*i]=2*i
        if s[i]=='G':
            g.append(i)
            gdict[2*i]=2*i
        if s[i]=='B':
            b.append(i)
            bdict[2*i]=2*i
    ans=len(r)*len(g)*len(b)
    for i in r:
        for j in g:
            if i+j in bdict:
                ans-=1
    for i in g:
        for j in b:
            if i+j in rdict:
                ans-=1
    for i in b:
        for j in r:
            if i+j in gdict:
                ans-=1
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from itertools import accumulate
from collections import defaultdict
import sys
input=sys.stdin.readline
N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
if K==1:
  print(0)
  exit()
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)


### FIXED CODE ###

import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n+1):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)