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

def getsum(BITTree, i):
    s = 0
    i = i + 1
    while i > 0:
        s += BITTree[i]
        i -= i & (-i)
    return s
def updatebit(BITTree, n, i, v):
    i += 1
    while i <= n:
        BITTree[i] += v
        i += i & (-i)
def construct(arr, n):
    BITTree = [0] * (n + 1)
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])
    return BITTree
n,k=map(int,input().split())
c=[]
a=[0]*(n+1)
a[1]=1
BITTree = construct(a,len(a))
mod=998244353
for i in range(k):
    x,y=map(int,input().split())
    c.append([x,y])
for i in range(2,n+1):
    for j in range(len(c)):
        p,q=c[j][0],c[j][1]
        if i-q>0:
            l,r=i-p,i-q
            z=(getsum(BITTree,l)-getsum(BITTree,r-1))%mod
            a[i]+=z
            updatebit(BITTree, len(a), i,z)
        else:
            q=i-1
            if i-q>0 and i-p>0:
                l, r = i - p, i - q
                z = (getsum(BITTree, l) - getsum(BITTree, r - 1))%mod
                a[i]+=z
                updatebit(BITTree, len(a), i, z)
print(a[n]%mod)








### FIXED CODE ###

def getsum(BITTree, i):
    s = 0  # initialize result

    # index in BITree[] is 1 more than the index in arr[]
    i = i + 1

    # Traverse ancestors of BITree[index]
    while i > 0:
        # Add current element of BITree to sum
        s += BITTree[i]

        # Move index to parent node in getSum View
        i -= i & (-i)
    return s


# Updates a node in Binary Index Tree (BITree) at given index
# in BITree. The given value 'val' is added to BITree[i] and
# all of its ancestors in tree.
def updatebit(BITTree, n, i, v):
    # index in BITree[] is 1 more than the index in arr[]
    i += 1

    # Traverse all ancestors and add 'val'
    while i <= n:
        # Add 'val' to current node of BI Tree
        BITTree[i] += v

        # Update index to that of parent in update View
        i += i & (-i)

    # Constructs and returns a Binary Indexed Tree for given


# array of size n.
def construct(arr, n):
    # Create and initialize BITree[] as 0
    BITTree = [0] * (n + 1)

    # Store the actual values in BITree[] using update()
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])

        # Uncomment below lines to see contents of BITree[]
    # for i in range(1,n+1):
    #     print BITTree[i],
    return BITTree


n,k=map(int,input().split())
c=[]
a=[0]*(n+1)
a[1]=1
BITTree = construct(a,len(a))
mod=998244353
for i in range(k):
    x,y=map(int,input().split())
    c.append([x,y])

for i in range(2,n+1):
    for j in range(len(c)):
        p,q=c[j][0],c[j][1]
        if i-q>0:
            l,r=i-p,i-q

            z=(getsum(BITTree,l)-getsum(BITTree,r-1))%mod

            a[i]+=z
            updatebit(BITTree, len(a), i,z)

        else:
            q=i-1
            if i-q>0 and i-p>0:
                l, r = i - p, i - q

                z = (getsum(BITTree, l) - getsum(BITTree, r - 1))%mod
                ##z= getsum(BITTree, q) - getsum(BITTree, p - 1)
                ##print(z)
                a[i]+=z
                updatebit(BITTree, len(a), i, z)
                ##print(BITTree)

##print(a)
print(a[n]%mod)
### BUGGY CODE ###

import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())

a = list(map(int, input().split()))

a_n = np.array(a)

for i in range(n):
    b = np.where(a_n == i+1, 1, 0)
    print(b.sum())

### FIXED CODE ###

import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())

a = list(map(int, input().split()))

a_n = np.array(a)
cnt_np = np.zeros(n)

for an in a:
    cnt_np[an-1] += 1
for cnt in cnt_np:
    print(int(cnt))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import copy

def solve(N: int, A: "List[List[int]]"):
    B = copy.deepcopy(A)
    for start_node in range(0,N):
        for end_node in range(start_node+1,N):
            min_dist = 10**12
            for transit in range(N):
                if transit == start_node or transit == end_node:
                    continue
                min_dist = min(min_dist,A[start_node][transit]+A[transit][end_node])

            ## impossible
            if A[start_node][end_node] > min_dist:
                print(-1)
                return 
            elif A[start_node][end_node] == min_dist:
                B[start_node][end_node] = 0
            else:
                continue
    answer =0
    for i in range(N):
        for j in range(i+1,N):
            answer+=B[i][j]
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import copy

def solve(N: int, A: "List[List[int]]"):
    B = copy.deepcopy(A)
    for start_node in range(0,N):
        for end_node in range(start_node+1,N):
            min_dist = 10**12
            for transit in range(N):
                if transit == start_node or transit == end_node:
                    continue
                min_dist = min(min_dist,A[start_node][transit]+A[transit][end_node])

            ## impossible
            if A[start_node][end_node] > min_dist:
                print(-1)
                return 
            elif A[start_node][end_node] == min_dist:
                B[start_node][end_node] = 0
            else:
                continue
    answer =0
    for i in range(N):
        for j in range(i+1,N):
            answer+=B[i][j]
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

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

n = int(input())
s = [1 if i=="R" else 2 if i=="G" else 4 for i in input()]
c = 0
for i in range(n-3):
    a = s[i]
    for j in range(i+1, n-1):
        if a == s[j]:
            continue
        else:
            b = a + s[j]
            c += sum([1 for k in range(j+1, n) if b+s[k]==7 and k-j!=j-i])
print(c)

### FIXED CODE ###

n = int(input())
s = [1 if i=="R" else 2 if i=="G" else 4 for i in input()]
r = s.count(1)
g = s.count(2)
b = s.count(4)
ans = r*g*b
for i in range(n-1):
    for j in range(1, (n-i-1)//2+1):
        if s[i] + s[i+j] + s[i+j+j] == 7:
            ans -= 1
print(ans)
### BUGGY CODE ###

def calc(a, b):
  return a ** 5 - b ** 5

x = int(input())
flag = 0
a = 1
b = 0
while (True):
  while (True):
    if calc(a,b) == x:
      flag = 1
      break
    b -= 1
  if flag == 1:
    break
  a += 1
  b = a - 1
print(a, b)
      

### FIXED CODE ###

def calc(a, b):
  return a ** 5 - b ** 5

x = int(input())
even = 0
if x % 2 == 0:
  even = 1
flag = 0
if even:
  a = 2
else:
  a = 1
b = 0
while (True):
  while (True):
    if calc(a,b) == x:
      flag = 1
      break
    elif calc(a,b) > x:
      break
    b -= 2
  if flag == 1:
    break
  a += 1
  if even:
    b = a - 2
  else:
    b = a - 1
print(a, b)
### BUGGY CODE ###

n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)

for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1

        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1

        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1

        elif(i >= y - 1):
            ans[j - i - 1] += 1

for i in ans:
    print(i)

### FIXED CODE ###

n, x, y = input().split(" ")
n, x, y = int(n), int(x), int(y)
ans = [0] * (n - 1)

for i in range(n - 1):
    for j in range(i + 1, n):
        now = 0
        if (j <= x - 1):
            ans[j - i - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i <= x - 1):
            now = now + x - 1 - i
            if (j - (x - 1) >= (y - 1) - j + 1):
                now = now + (y - 1) - j + 1
            else:
                now = now + j - (x - 1)
            ans[now - 1] += 1

        elif(j > x - 1 and j <= y - 1 and i > x - 1):
            if (j - i >= (i - (x - 1)) + ((y - 1) - j) + 1):
                now = (i - (x - 1)) + ((y - 1) - j) + 1
            else:
                now = j - i
            ans[now - 1] += 1

        elif(j > y - 1 and i <= x - 1):
            now = now + x - 1 - i
            now = now + j - (y - 1) + 1
            ans[now - 1] += 1

        elif(j > y - 1 and i > x - 1 and i < y - 1):
            if((y - 1) - i >= i - (x - 1) + 1):
                now = now + i - (x - 1) + 1
            else:
                now = now + (y - 1) - i
            now = now + j - (y - 1)
            ans[now - 1] += 1

        elif(i >= y - 1):
            ans[j - i - 1] += 1
print(*ans)
### BUGGY CODE ###

INT_MAX = (1<<31) - 1
def update():
    for i in range(_N):
        x = i+N-1
        A_bin_tree[x] = arr[i]
        while x > 1:
            x >>= 1
            y = x<<1
            l = A_bin_tree[y]
            r = A_bin_tree[y+1]
            A_bin_tree[x] = l if l < r else r#min(l,r)

def find(x,y):
    l = x+N-1
    r = y+N-1
    z = INT_MAX
    while l < r:
        if l & 1:
            if(A_bin_tree[l] < z):
                z = A_bin_tree[l]
            l += 1
        if r & 1:
            r -= 1
            if(A_bin_tree[r] < z):
                z = A_bin_tree[r]
        l >>= 1
        r >>= 1
    return z

import sys
input = sys.stdin.readline
_N,k = map(int,input().split())
*arr, = map(int,input().split())
N = 1
N = 2**(_N-1).bit_length()
A_bin_tree = [INT_MAX]*(N<<1)
update()
res = [find(i,i+k) for i in range(_N-k+1)]
print(*res)


### FIXED CODE ###

INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r#min(tree[left],tree[right])
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m, p = map(int, input().split())
edge = []
edge_inv = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b, -c+p))
    edge_inv[b].append(a)


visited = [False] * n
def dfs(v):
    global visited
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))


### FIXED CODE ###

n, m, p = map(int, input().split())
graph = [[] for _ in range(n)]
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, -c+p))
    edge.append((a, b, -c+p))

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost

exist = True
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost
            if v_to == n - 1:
                exist = False

if not exist:
    print(-1)
else:
    print(max(0, -d[n-1]))
### BUGGY CODE ###

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * (3 ** q % p) % p       # ABC
        if q >= 1:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # ?BC
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 1) % p) % p # AB?
        if q >= 2:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # ?B?
        ans %= p
    elif s[i] == '?':
        if q >= 1:
            ans += (l_a[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # A?C
        if q >= 2:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 2) % p) % p # ??C
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # A??
        if q >= 3:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 3) % p) % p # ???
        ans %= p

print(ans)


### FIXED CODE ###

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p # ???
        ans %= p

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

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
f_inf = float('inf')

dp = [f_inf] * (10**5+10)

dp[0] = 0
for i in range(1, n):
    for j in range(1, k+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i-j]+ abs(h[i] - h[i - j]))

print(dp[n-1])

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

f_inf = float('inf')
dp = np.zeros(n, dtype=int)
h = np.array(h)
for i in range(1, n):
    start = max(0, i - k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
inf = 10**9
dp = np.zeros((M + 1, 2**N), dtype = 'int') + inf 
# dp[i][j] := i個目までの鍵を使うときの状態jを実現する最小費用 # 0列目は使わない
# 行 : 0番目の鍵 ~ M - 1番目の鍵
# 列 : 状態0 ~ 2**N - 1

dp[0][0] = 0

for i in range(1, M + 1):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    d = 0 # i番目の鍵が開けられる宝箱の状態
    for c in c_ls:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = np.bitwise_or(j, d)
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        dp[i][jord] = min(dp[i - 1][j] + a, dp[i][jord])
#         if i == 1:
#             print(dp[i][jord], i, jord, j, d, np.bitwise_or(j, d))
        
if dp[M][2**N - 1] == inf:
    print(- 1)
else:
    print(dp[M][2**N - 1])

### FIXED CODE ###

N, M = map(int, input().split())

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))    
    for j in range(2**N):
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])
### BUGGY CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

buf = []
cnt = []
for i in s:
    if i not in buf:
        buf.append(i)
        cnt.append(0)
    cnt[buf.index(i)] += 1

ans = [i for i, x in enumerate(cnt) if x == max(cnt)]

ans2 = [buf[i] for i in range(len(buf)) if i in ans]

ans3 = sorted(ans2)

for i in ans3:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### BUGGY CODE ###

N = int(input())
s = [int(input()) for i in range(N)]

def dfs(i, score):
    global ans
    if i == N:
        if score % 10 != 0:
            ans = max(ans, score)
            
    else:
        dfs(i+1, score)
        dfs(i+1, score+s[i])

ans = 0
dfs(0, 0)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
s = sorted([int(input()) for i in range(N)])

correct = False
for n in s:
    if n % 10 != 0:
        correct = True
        break

if correct:
    ans_max = sum(s)
    if ans_max % 10 != 0:
        print(ans_max)
    else:
        for i in s:
            if i % 10 != 0:
                print(ans_max-i)
                break
else:
    print(0)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(3001):
    if N - r * R < 0:
        continue
    for g in range(3001):
        tmp = N - r * R - g * G
        if tmp < 0:
            break
        if tmp % B == 0 and tmp // B >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N // R + 1):
    for g in range((N - R * r) // G + 1):
        tmp = N - r * R - g * G
        if tmp % B == 0:
            ans += 1

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

from bisect import bisect_left

R = lambda: map(int, input().split())
n, m = R()
a = sorted(R())
for _ in range(m):
    b, c = R()
    l = bisect_left(a, c)
    for i in range(b, l):
        a[i - b] = a[i]
    for i in range(max(0, l - b), l):
        a[i] = c
print(sum(a))


### FIXED CODE ###

import heapq
from itertools import repeat, starmap
from operator import mul

R = lambda: map(int, input().split())
n, m = R()
a = list(zip(R(), repeat(1)))
heapq.heapify(a)
for _ in range(m):
    b, c = R()
    i = b
    while i:
        x, y = a[0]
        if x >= c:
            break
        heapq.heappop(a)
        d = min(i, y)
        i -= d
        y -= d
        if y:
            heapq.heappush(a, (x, y))
    heapq.heappush(a, (c, b - i))
print(sum(starmap(mul, a)))
### BUGGY CODE ###

# 初期入力
N = int(input())
word = [ input() for i in range(N) ]

# 単語をキーに数を数えて辞書
from collections import Counter
kazu_word = Counter(word)

#一番多い単語を抜き出す
kazu_word_max =[i for i,v in kazu_word.items() if v == max(kazu_word.values())]
kazu_word_max.sort()
"""
print(kazu_word)
print(kazu_word_max)
"""
print(*kazu_word_max,sep="\n")

### FIXED CODE ###

# 初期入力
N = int(input())
word = [ input() for i in range(N) ]

# 単語をキーに数を数えて辞書
from collections import Counter
kazu_word = Counter(word)

#一番多い単語を抜き出す
kazu_word_a = max(kazu_word.values()) #　内包表記の中で毎回MAXを計算するより出したほうが１回で済む
kazu_word_max =[i for i,v in kazu_word.items() if v == kazu_word_a ]
kazu_word_max_sorted = sorted(kazu_word_max)
"""
print(kazu_word)
print(kazu_word_max)
"""
print(*kazu_word_max_sorted,sep="\n")
### BUGGY CODE ###

N,K= map(int, input().split())
List = list(map(int, input().split()))
num=0
for i in range(0,N-K+1):
    a=0
    for u in range(K):
        a+=(List[i+u]+1)
    a=a/2
    if a>=num:
        num=a
print(num)

### FIXED CODE ###

N,K= map(int, input().split())
List = list(map(int, input().split()))
num=0
s=0
for i in range(K):
    s+=(List[i]+1)
num=0
#print(s)
if N==K:
    print(s/2)
else:
    
    for i in range(N-K):
        a=List[i+K]-List[i]
        #print(a)
        n1=s+a
        s=n1
        n1=n1/2
        if n1>=num:
            num=n1
    print(num)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# 入力を各変数に格納
n, m = map(int, input().split())

cells = [[1 for i in range(n)] for j in range(m)]

# カードを裏返す関数
def turnCard(_y, _x):

    global cells

    if cells[_y][_x] == 0:
        cells[_y][_x] = 1
    elif cells[_y][_x] == 1:
        cells[_y][_x] = 0

# 各マスを周回して8方向に裏返し処理
for y in range(m):
    for x in range(n):

        # そのマスを裏返す
        turnCard(y, x)
        # 左端以外
        if x != 0:
            # 左隣を裏返す
            turnCard(y, x-1)
        # 右端以外
        if x != n-1:
            # 右隣を裏返す
            turnCard(y, x+1)
        # 最上段以外
        if y != 0:
            # ひとつ上を裏返す
            turnCard(y-1, x)
        # 最下段以外
        if y != m-1:
            # ひとつ下を裏返す
            turnCard(y+1, x)
        # 左端と最上段以外
        if x != 0 and y != 0:
            # 左斜め上を裏返す
            turnCard(y-1, x-1)
        # 右端と最上段以外
        if x != n-1 and y != 0:
            # 右斜め上を裏返す
            turnCard(y-1, x+1)
        # 左端と最下段以外
        if x != 0 and y != m-1:
            # 左斜め下を裏返す
            turnCard(y+1, x-1)
        # 右端と最下段以外
        if x != n-1 and y != m-1:
            # 右斜め下を裏返す
            turnCard(y+1, x+1)
        
# 各マスを周回して裏のマスで+1
ans = 0
for y in range(m):
    for x in range(n):
        if cells[y][x] == 0:
            ans += 1
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

# 入力を各変数に格納
n, m = map(int, input().split())

ans = 0

# 行列ともに1
if n == 1 and m == 1:
    ans = 1
# 行が1
elif n == 1:
    ans = m - 2
# 列が1
elif m == 1:
    ans = n - 2
# 行列とも1ではない
else:
    ans = (n - 2) * (m - 2)

print(ans)