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

import sys

def prime(n):
    N = n + 1
    ints = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(N)]
    try:
        ints[0] = ints[1] = False
        ints[2] = ints[3] = ints[5] = True
    except IndexError:
        pass
    sqrt = N ** 0.5

    for i in range(3, N, 2):
        if i >= sqrt:
            break
        for m in range(i ** 2, N, i):
            ints[m] = False
    return ints.count(True)

for line in sys.stdin:
    print(prime(int(line)))

### FIXED CODE ###

import sys

def sieve(n):
    N = n + 1
    ints = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(N)]
    try:
        ints[0] = ints[1] = False
        ints[2] = ints[3] = ints[5] = True
    except IndexError:
        pass
    sqrt = N ** 0.5

    for i in range(3, N, 2):
        if i >= sqrt:
            break
        for m in range(i ** 2, N, i):
            ints[m] = False
    return ints

prime1m = sieve(1000000)

for line in sys.stdin:
    print(prime1m[:int(line) + 1].count(True))
### BUGGY CODE ###

def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 7)

    def dfs(v, dist):
        for u in g[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                dfs(u, dist)

    N, u, v = map(int, input().split())
    u -= 1
    v -= 1

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    dist_from_a = [-1] * N
    dist_from_a[v] = 0
    dfs(v, dist_from_a)

    q = deque()
    q.append((u, -1, 0))

    while q:
        t, p, cost = q.popleft()
        for next_t in g[t]:
            if next_t == p:
                continue
            if dist_from_a[next_t] > cost + 1:
                q.append((next_t, t, cost + 1))
            elif dist_from_a[next_t] == cost:
                # 奇数距離で会う
                # cost+1//2とtとnext_tの間の辺を削除したグラフでtから最も遠い点までの距離の和
                x = t
                g[t].remove(next_t)
                g[next_t].remove(t)
                d_to_x = cost
                q = []
                break
            elif dist_from_a[next_t] == cost + 1:
                # 偶数距離で会う
                # cost+1//2とtとnext_tの間の辺を削除したグラフでtから最も遠い点までの距離の和
                x = t
                g[t].remove(next_t)
                g[next_t].remove(t)
                d_to_x = cost + 1
                q = []
                break

    dist_from_x = [-1] * N
    dist_from_x[x] = 0

    dfs(x, dist_from_x)
    d = max(dist_from_x)
    print(d + d_to_x)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説を見た

def solve(N, t, a, g) -> int:
    import sys

    sys.setrecursionlimit(10 ** 7)

    def calc_dist(init):
        dist = [-1] * N
        dist[init] = 0

        def _calc_dist(curr):
            for next_ in g[curr]:
                if dist[next_] != -1:
                    continue
                dist[next_] = dist[curr] + 1
                _calc_dist(next_)

        _calc_dist(init)
        return dist

    dist_a = calc_dist(a)
    dist_t = calc_dist(t)

    return max(dist_a[v] for v in range(N) if dist_t[v] < dist_a[v]) - 1


if __name__ == '__main__':
    N, t, a = map(int, input().split())
    t -= 1
    a -= 1

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    print(solve(N, t, a, g))

# 青木君からの距離 > 高橋君からの距離 となる頂点Xが目的地の候補
# 青木君と高橋君の共通祖先からの距離は等しいので、
# 共通祖先への距離は、 青木君 > 高橋君 となり、高橋君は必ずXに到達できる
# Xに着いた高橋君は、手前の頂点とXとを行ったり来たりする
# a-t->at-: aが一歩進んだときに高橋君に会う(-は無人のマス目)
# at: tが手前の頂点に移動したときに青木君に会う
# いずれも手前の頂点まで青木君が移動したときにゲームが終わる
# どのXを選んでも、Xの手前でゲームが終わるので、青木君から最も遠いXを選ぶのが最善
# 頂点X: 追いつめられる位置=葉
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        if v in G[c]:
            G[c].remove(v)
        stack.append(c)
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].add(B)
    G[B].add(A)
if M % 2 == 1:
    print(-1)
    exit()
G2 = [set() for _ in range(N+1)]
parent = [0] * (N+1)
depth = [-1] * (N+1)
depth[1] = 0
stack = [1]
while stack:
    v = stack.pop()
    if len(G[v]) > 0 and v != 1:
        depth[v] = depth[parent[v]] + 1
    for c in G[v]:
        G2[v].add(c)
        parent[c] = v
        if v in G[c]:
            G[c].remove(v)
        stack.append(c)
    G[v] = set()
nodes = sorted(list(range(1, N+1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
    for c in G2[v]:
        ans.append((v, c))
    if len(G2[v]) % 2 == 1:
        p = parent[v]
        ans.append((v, p))
        G2[p].remove(v)
for u, v in ans:
    print(u, v)
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A, dtype=np.int64)

for _ in range(0, min(42, K)):
    B = np.zeros(N, dtype=np.int64)
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if (r + 1 < N):
            B[r + 1] -= 1
    A = np.cumsum(B)
    if (np.all(A == N)):
        break;

print(" ".join([str(item) for item in A]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = []

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res.append((r-l)*(u-d))

print(min(res))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    if res < (r-l)*(u-d):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)
### BUGGY CODE ###

MASK=10**9+7
N,K=map(int,input().split())

def cmb(n,r):
  t=1
  for i in range(r):
    t *= n-i
  for i in range(r,1,-1):
    t //= i
  return t

for i in range(0,K):
  print((cmb(N+1-K,i+1)*cmb(K-1,i))%MASK)


### FIXED CODE ###

MASK=10**9+7
N,K=map(int,input().split())

F=[1]*(N+1)
for i in range(1,N+1):
  F[i] = i* F[i-1]

def cmb(n,r):
  return F[n]//F[r]//F[n-r]

for i in range(0,K):
  print((cmb(N+1-K,i+1)*cmb(K-1,i))%MASK)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
exp, max_exp = 0, 0
def calc_exp(p):
  # calculate expectation
  dice = []
  for a in range(p):
    dice.append(a + 1)
  exp = float(sum(dice) / p)
  return exp
for i in range(N - K + 1):
  k, exp = 0, 0
  while k <= K - 1:
    exp += calc_exp(P[i + k])
    k += 1
  max_exp = max(max_exp, exp)
print(max_exp)

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
acc = [0] + list(accumulate(P))
print((max(b - a for a, b in zip(acc, acc[K:])) + K) / 2)
### BUGGY CODE ###

from collections import deque
 
n = int(input())
 
connect_list = [[] for _ in range(n)]
 
ab = [list(map(int, input().split())) for i in range(n-1)]
 
for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)
 
 
color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n
 
color_max = 1
 
d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1
 
    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))
 
    color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])
    # print("clr:", color_list_rest)
 
    for i in index_list:
        if color_list[index][i] == -1:
            num = color_list_rest.pop()
            color_list[index][i] = num
            color_list[i][index] = num
 
    for i in index_list:
        if check_list[i] == 0:
            check_list[i] = 1
            d.append(i)
 
print(color_max)
for a, b in ab:
    print(color_list[a-1][b-1])

### FIXED CODE ###

#!/usr/bin/env python3

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

ab = [list(map(int, input().split())) for i in range(n-1)]

for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)


color_list = {}
check_list = [0]*n

color_max = max(map(len, connect_list))

vertex = [0 for i in range(n)]
d = deque([0])

while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]

    for i in index_list:
        if check_list[i] == 1:
            continue

        check_list[i] = 1
        d.append(i)
        num = vertex[index] % color_max+1
        color_list[(min(index, i), max(index, i))] = num
        vertex[index], vertex[i] = num, num


print(color_max)
for a, b in ab:
    print(color_list[(a-1, b-1)])
### BUGGY CODE ###

n = int(input())
a=[int(i) for i in input().split()]

ans=0
for i in set(a):
  if a.count(i)-i<0:
    ans+=a.count(i)
  else:
    ans+=a.count(i)-i
  
print(ans)




### FIXED CODE ###

import collections

n = int(input())
a=[int(i) for i in input().split()]
#a.sort()

c = collections.Counter(a)

#print(c)
ans=0
for i in set(a):
  tmp=c[i]
  if tmp-i<0:
    ans+=tmp
  else:
    ans+=tmp-i
  
print(ans)
### BUGGY CODE ###

from fractions import gcd
def solve():
    K = int(input())

    ans = 0
    for a in range(1,K+1):
        for b in range(1,K+1):
            for c in range(1,K+1):
                ans += gcd(gcd(a,b), c)
    
    print(ans)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

from math import gcd
def solve():
    K = int(input())

    ans = 0
    for a in range(1,K+1):
        for b in range(1,K+1):
            for c in range(1,K+1):
                ans += gcd(gcd(a,b), c)
    
    print(ans)

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

import numpy as np
n,q = map(int,input().split())
s = str(input())
k = np.array([ 1 if s[i-1] == "A" and s[i] == "C" else 0  for i in range(n)])
#print(k)
for i in range(q):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    #print(k[a:b+1])
    ans = np.sum(k[a:b+1])
    if k[a] == 1:
        ans -= 1
    print(ans)

### FIXED CODE ###

from itertools import *
n,q = map(int,input().split())
s = str(input())
k = [ 1 if s[i-1] == "A" and s[i] == "C" else 0  for i in range(n)]
cumsum = list(accumulate(k))
#print(k)
#print(cumsum)
for i in range(q):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    #print(k[a:b+1])
    ans = cumsum[b] - cumsum[a]
    """
    if k[a] == 1:
        ans -= 1
    """
    print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM


STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0


listM=[int(input()) for i in range(M)]
dp[0] = 1

for i in range(N):
    for k in range(1, STEP+1):
        if i+k > N:
            break
        if isSafe(i+k):
            dp[i+k] += dp[i]
            
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)

### FIXED CODE ###


import sys
input = sys.stdin.readline
def isSafe(position):
    return not position in listM
 
 
STEP = 2
N,M = map(int,input().split())
dp = [0] * (N+1)
cnt = 0
 
 
listM={int(input()) for i in range(M)}
dp[0] = 1
 
for i in range(N):
    if i+1 > N:
        break
    if isSafe(i+1):
        dp[i+1] += dp[i]
    if i+2 > N:
        break
    if isSafe(i+2):
        dp[i+2] += dp[i]
        #dp[j] = 0
    #print(dp)
        
print(dp[N] % 1000000007)
### BUGGY CODE ###

# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
B = np.full((H,W),-1,dtype=int)

queue = []

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

while queue!=[]:
    I,J = queue.pop(0)
    for i,j in [(I-1,J),(I+1,J),(I,J-1),(I,J+1)]:
        if i>=0 and i<H and j>=0 and j<W and B[i][j]<0:
            B[i][j] = B[I][J]+1
            queue.append((i,j))

print(np.max(B))

### FIXED CODE ###

# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

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

from collections import defaultdict
# from sys import stdin
# input = stdin.readline


def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  # dp = [0]*(len(S)+1)
  # dp[0] = 0
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    # dp[i] = (dp[i-1] + ten*int(s)) % MOD
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10

  sum_ = 0
  # for sup in dp:
  #   dic[sup] += 1

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  # dp = [0]*(len(S)+1)
  # dp[0] = 0
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    # dp[i] = (dp[i-1] + ten*int(s)) % MOD
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10
    ten %= MOD

  sum_ = 0
  # for sup in dp:
  #   dic[sup] += 1

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


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

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    x = a[mi-1]
    if x >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[k-x:k]):
        ba = mi
    else:
        fr = mi

print(fr)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)
### BUGGY CODE ###

def main():
    H = int(input())
    n = 1
    ans = 0
    a = 1
    while a == 1:
        H = H // 2
        n += 1
        if H == 1:
            ans = 2 ** n - 1
            break
    print(ans)
main()


### FIXED CODE ###

def main():
    H = int(input())
    n = 1
    ans = 0
    a = 1
    while H != 1:
        H = H // 2
        n += 1
    print(2 ** n - 1)
main()
### BUGGY CODE ###

import numpy
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  for i in range(m):
    a[-1]=a[-1]//2
    a.sort()
  print(sum(a))
main()


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[-_ for _ in a]
import heapq
heapq.heapify(a)
for i in range(m):
  temp=-heapq.heappop(a)
  heapq.heappush(a,-(temp//2))
  
print(-sum(a))
### BUGGY CODE ###

import itertools
import copy


class Deque:
    def __init__(self, default_deque: list):
        self.in_hand = []
        self.deque = default_deque

    def operation(self, operation_type: str):
        if operation_type == "A":
            self.in_hand.append(self.deque[0])
            del self.deque[0]
        elif operation_type == "B":
            self.in_hand.append(self.deque[-1])
            del self.deque[-1]
        elif operation_type == "C":
            self.deque.insert(0, min(self.in_hand))
            _index = self.in_hand.index(min(self.in_hand))
            del self.in_hand[_index]
        elif operation_type == "D":
            self.deque.append(min(self.in_hand))
            _index = self.in_hand.index(min(self.in_hand))
            del self.in_hand[_index]


if __name__ == '__main__':
    max_repeat_count = int(input().split()[1])
    value_list = list(map(int, input().split()))
    point_list = []
    for repeat_count in range(max_repeat_count+1):
        operation_pattern_iter = itertools.product(["A", "B", "C", "D"], repeat=repeat_count)
        for operation_pattern in operation_pattern_iter:
            deque = Deque(copy.copy(value_list))
            for operation in operation_pattern:
                try:
                    deque.operation(operation)
                except:
                    break
            else:
                point_list.append(sum(deque.in_hand))

    print(max(point_list))



### FIXED CODE ###

import itertools
import copy


class Deque:
    def __init__(self, default_deque: list, max_count: int):
        self.in_hand = []
        self.deque = default_deque
        self.operation_count = 0
        self.max_count = max_count

    def operation(self, operation_type: str):
        if operation_type == "A":
            self.in_hand.append(self.deque[0])
            del self.deque[0]
            self.operation_count += 1
        elif operation_type == "B":
            self.in_hand.append(self.deque[-1])
            del self.deque[-1]
            self.operation_count += 1
        elif operation_type == "C":
            self.in_hand.sort()
            for i in range(self.max_count - self.operation_count):
                if self.in_hand[0] < 0:
                    del self.in_hand[0]
                else:
                    return


if __name__ == '__main__':
    max_repeat_count = int(input().split()[1])
    value_list = list(map(int, input().split()))
    point_list = []
    for repeat_count in range(max_repeat_count+1):
        operation_pattern_iter = itertools.combinations_with_replacement(["A", "B"], repeat_count)
        for operation_pattern in operation_pattern_iter:
            deque = Deque(copy.copy(value_list), max_repeat_count)
            for operation in operation_pattern:
                try:
                    deque.operation(operation)
                except:
                    break
            else:
                try:
                    deque.operation("C")
                    point_list.append(sum(deque.in_hand))
                except:
                    point_list.append(sum(deque.in_hand))
                    break
    print(max(point_list))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    res = 0
    maxI = 0
    maxV = 0
    for i in range(N-K+1):
        v = sum(P[i:i+K])
        if v > maxV:
            maxV = v
            maxI = i
    res = (sum(P[maxI:maxI+K]) + K) / 2.0
    print(res)

main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    maxI = 0
    maxV = sum(P[:K])
    curV = maxV
    for i in range(1, N-K+1):
        curV = curV + P[i+K-1] - P[i-1]
        if curV > maxV:
            maxV = curV
            maxI = i

    res = (sum(P[maxI:maxI+K]) + K) / 2.0
    print(res)

main()
### BUGGY CODE ###

import itertools


max_num = 10000
num_list = [i for i in range(-max_num,  max_num+1)]
num_list_5 = [i ** 5 for i in num_list]
num_comb = list(itertools.combinations(num_list, 2))

x = int(input().strip())
for comb in num_comb:
    a = comb[0]
    b = comb[1]
    a5 = num_list_5[a]
    b5 = num_list_5[b]
    if a5 - b5 == x:
        print(num_list[a], num_list[b])
        break

### FIXED CODE ###

import itertools


max_num = 200
num_list = [i for i in range(-max_num,  max_num+1)]
num_comb = list(itertools.permutations(num_list, 2))

x = int(input().strip())
for comb in num_comb:
    a = comb[0]
    b = comb[1]
    # print(a, b)
    a5 = a ** 5
    b5 = b ** 5
    if a5 - b5 == x:
        print(a, b)
        break
### BUGGY CODE ###

s=[int(x) for x in list(input())]
for c in range(len(s)-1,-1,-1):
    if c==len(s)-1:
        continue
    s[c]=((10**(len(s)-c-1))*s[c]+s[c+1])%2019
s.append(0)
s.sort()
h=[1]
d=s[0]
for c in range(1,len(s)):
    if s[c]!=d:
        h.append(1)
        d=s[c]
    else:
        h[-1]+=1
k=[(x*(x-1))//2 for x in h]
print(sum(k))

### FIXED CODE ###

s=[int(x) for x in list(input())]
for c in range(len(s)-1,-1,-1):
    if c==len(s)-1:
        continue
    s[c]=(pow(10,len(s)-c-1,2019)*s[c]+s[c+1])%2019
s.append(0)
s.sort()
h=[1]
d=s[0]
for c in range(1,len(s)):
    if s[c]!=d:
        h.append(1)
        d=s[c]
    else:
        h[-1]+=1
k=[(x*(x-1))//2 for x in h]
print(sum(k))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [i+1+A[i] for i in range(N)]
C = [i+1-A[i] for i in range(N)]
ans = 0
for j in range(N):
    ans += C[j:].count(B[j])
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
B = Counter(list(i+1+A[i] for i in range(N)))
#print(B,B[3])
C = Counter((i+1-A[i] for i in range(N)))
ans = 0
#print(C)
for j in range(N):
    ans += B[j]*C[j]
print(ans)