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

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

ll.sort()

def binary_search(arr, l, r, x):
    if r-l <= 0:
        return l
    
    else:
        mid = (l + r) // 2
        if arr[mid] == x:
            return mid
    
        elif arr[mid] > x:
            return binary_search(arr, l, mid-1, x)

        else:
            return binary_search(arr, mid+1, r, x)

ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        c = ll[i] + ll[j]
        limit = binary_search(ll, j+1, n, c)
        ans += limit - j - 1

print(ans)

### FIXED CODE ###

n = int(input())
ll = list(map(int, input().split()))
from bisect import bisect_left

def binary_search(arr, low, high, x):
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x: low = mid+1
        else: high = mid

    return low


def rec_binary_search(arr, l, r, x):
    if r-l <= 0:
        return l
    
    else:
        mid = (l + r) // 2
        if arr[mid] == x:
            return mid
    
        elif arr[mid] > x:
            return binary_search(arr, l, mid-1, x)

        else:
            return binary_search(arr, mid+1, r, x)

ll.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        c = ll[i] + ll[j]
        limit = bisect_left(ll, c)
        ans += limit - j - 1

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

from fractions import gcd
from functools import reduce

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

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num // v for v in A) % MOD)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

def lcm(x, y):
    return x * y // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num * pow(v, MOD - 2, MOD) for v in A) % MOD)
### BUGGY CODE ###

import math
def combinations_count(n, r):
    if n >= 2:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0
N = int(input())
A = [int(a) for a in input().split()]
a = [0] * N
for i in A:
    a[i-1] += 1
sum = 0
for i in range(N):
    sum += combinations_count(a[i], 2)
for k in range(N):
    print(sum +  combinations_count(a[A[k]-1]-1, 2) - combinations_count(a[A[k]-1], 2))


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
a = [0] * N
for i in A:
    a[i-1] += 1
cnt = 0
cnt += sum([i*(i-1)//2 for i in a])
for i in A:
    print(cnt - (a[i-1]-1))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [1 if s[i:i+2]=='AC' else 0 for i in range(n-1)]
    
for l,r in lr:
  print(sum(ac[l-1:r-1]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [0]*(n+1)

for i in range(1,n+1):
  if s[i-1:i+2-1]=='AC':  
    ac[i]=ac[i-1] + 1
  else:
    ac[i]=ac[i-1]
    
for l,r in lr:
  print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

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

mx = 1e18
pr = 1
done = True

for i in a:
	pr = pr*i

if pr <= mx:
	print(pr)
else:
	print(-1)

### FIXED CODE ###

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

mx = 1e18
pr = 1
done = True
zero = False

for i in a:
	if i == 0:
		zero = True

if zero == False:
	for i in a:
		pr = pr*i
		if pr > mx:
			break
else:
	pr = 0
if zero or pr <= mx:
	print(pr)
else:
	print(-1)
### BUGGY CODE ###


import sys
from fractions import gcd
import bisect

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
s = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]



n, m = na()
a = na()
a.sort()

for i in range(m):
    b, c = na()
    for j in range(b):
        if a[0] < c:
            a.pop(0)
            inid = bisect.bisect_left(a, c)
            a.insert(inid, c)
        else:
            break

print(sum(a))

### FIXED CODE ###

import sys
import math
import numpy as np
import bisect
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
a = na()
bc = []

for _ in range(m):
    bci = na()
    bc.append(bci)

bc.sort(key=lambda x:x[1], reverse=True)
#print(bc)

bi, ci = bc[0][0], bc[0][1]
i = 0
for _ in range(n):
    if bi != 0:
        bi -= 1
        a.append(ci)
    else:
        i += 1
        if i > (m - 1):
            break
        else:
            bi, ci = bc[i][0], bc[i][1]
            bi -= 1
            a.append(ci)

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import math
X = int(input())
a = math.ceil(X**(1/5))
c = 0
N = int(1e10)
while c <= N:
    c += 1
    b = math.floor((a**5-X)**(1/5))
    if a**5 - b**5 == X:
        print(a, b)
        break
    a += 1

### FIXED CODE ###

import math
X = int(input())
a1 = math.ceil(X**(1/5))
N = int(1e10)
c = 0
b = 0
while c <= N:
    if b**5 < -X:
        b2 = b + 1
        break
    b -= 1
c = 0
while c <= N:
    c += 1
    b1 = math.floor((a1**5-X)**(1/5))
    a2 = math.floor((X+b2**5)**(1/5))
    if a1**5 - b1**5 == X:
        print(a1, b1)
        break
    elif a2**5 - b2**5 == X:
        print(a2, b2)
        break
    a1 += 1
    b2 += 1
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0
r = []
g = []
b = []
for i in range(n):
    if s[i]=='R':r.append(i)
    elif s[i]=='G':g.append(i)
    else:b.append(i)
for i in r:
    for j in g:
        for k in b:
            x,y,z = sorted([i,j,k])
            if y-x!=z-y:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0
r = []
g = []
b = []
for i in range(n):
    if s[i]=='R':r.append(i)
    elif s[i]=='G':g.append(i)
    else:b.append(i)
ans = len(r)*len(g)*len(b)
d = 0
for i in range(n-2):
    for j in range(i,n-1):
        k = j+j-i
        if k < n and s[i] != s[j] and s[k] != s[i] and s[k]!=s[j]:
            d+=1
print(ans-d)
### BUGGY CODE ###

import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = [a - c, 1, c]
	E[2*n + 1] = [b - c, -1, c]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = int(inputs())
flag = False
cont = False
for e in E:
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
		mini = min(e[2],mini)
	elif e[1] == -1:
		kouho.remove(e[2])
		cont = False
for t in [None]*(Q-q):
	print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

# D

x = int(input())

a = int(x**(1/5))
b = int(abs(x-a**5)**(1/5))
i = 1
while True:

    if a**5 - b**5 != x and a**5 - (-b)**5 != x:
        a = int(x**(1/5))+i
        b = int(abs(x-a**5)**(1/5))
        if a**5 - b**5 == x:
            print(a,b)
            break
        elif a**5 - (-b)**5 == x:
            print(a,-b)
            break
        else:
            i += 1
        
    elif a**5 - b**5 == x:
        print(a,b)
        break

    else:
        print(a,-b)
        break

    


### FIXED CODE ###

# D

x = int(input())

a = int(x**(1/5))
b = int(abs(x-a**5)**(1/5))
i = 1
while True:
    if a**5 - b**5 != x and a**5 - (-b)**5 != x:
        if a**5 - x > (a+1)**5 - x:
            a += i
            b = int(abs(x-a**5)**(1/5))
            if a**5 - b**5 == x:
                print(a,b)
                break
            elif a**5 - (-b)**5 == x:
                print(a,-b)
                break
            else:
                pass
        else:
            a -= 1
            b = int(abs(x-a**5)**(1/5))
            if a**5 - b**5 == x:
                print(a,b)
                break
            elif a**5 - (-b)**5 == x:
                print(a,-b)
                break
            else:
                pass
    elif a**5 - b**5 == x:
        print(a,b)
        break

    else:
        print(a,-b)
        break
### BUGGY CODE ###

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

#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        dp=[False for i in range(0,K)]
        for i in range(K-A[num],K):
            dp[i]=True

        for i in range(1,N):
            for j in range(0,K-test[i-1]):
                dp[j]=dp[j] or dp[j+test[i-1]]
        return dp[0]

#必要な数のうち最小のもの
if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)

### FIXED CODE ###

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

l=N
for i in range(0,N):
    if A[i]>=K:
        l=i
        break
A=A[:l]
N=l
#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        check=0
        for i in range(K-A[num],K):
            check+=pow(2,i)

        for i in range(1,N):
            check=check|(check>>test[i-1])

        return check%2==1
        

#必要な数のうち最小のもの
if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)
### BUGGY CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1
ans = r * g * b

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        x = j + j - i
        if S[i] != S[j] and x <= N - 1:
            if S[i] != S[x] and S[x] != S[j]:
                ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            x = 2 * j - i
            if x < N and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

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

X, K, D = map(int, input().split())

counter = 0

while (counter < K):
  if (X > 0):
    X = X - D
  else:
    X = X + D
  counter += 1

print(abs(X))


### FIXED CODE ###

X, K, D = map(int, input().split())

X = abs(X)

K_main = X // D
K_sub = K - K_main

if (K_sub < 0):
  print(abs(X - D * K))
else:
  answer = abs(X - D * K_main)
  if (K_sub % 2 == 0):
    print(answer)
  else:
    print(abs(answer -D))
### BUGGY CODE ###

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

already = [0 for i in range(n+1)]
idx = m+1
for sa in range(m)[::-1]:
    sa += 1
    while True:
        if idx-sa < 1:
            idx = sa + 1
            # if idx > n: idx = 1
            continue
        if already[idx] == 0 and already[idx-sa] == 0:
            right, left = idx, idx-sa
            already[right], already[left] = 1, 1
            idx += 1
            if idx > n: idx = 1
            break
        else:
            idx += 1
            if idx > n: idx = 1
    print(left, right)

### FIXED CODE ###

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

if m%2 == 0:
    gu_max, ki_max = m, m-1
else:
    gu_max, ki_max = m-1, m
gu_start = 1
ki_start = 1 + gu_max + 1

for sa in range(m)[::-1]:
    sa += 1
    if sa%2 == 0:
        print(gu_start, gu_start+sa)
        gu_start += 1
    else:
        print(ki_start, ki_start+sa)
        ki_start += 1
### BUGGY CODE ###

N = int(input())
A = input().split()

offset = 0 if N % 2 == 0 else 1
ans = A[0]
for i in range(1, N):
    if (i+offset) % 2 == 0:
        ans = ans + " " + A[i]
    else:
        ans = A[i] + " " + ans

print(ans)


### FIXED CODE ###

from collections import deque

N = int(input())
A = input().split()

offset = 0 if N % 2 == 0 else 1
ans = deque([A[0]])
for i in range(1, N):
    if (i+offset) % 2 == 0:
        ans.append(A[i])
    else:
        ans.appendleft(A[i])

print(" ".join(ans))
### BUGGY CODE ###

N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)

### FIXED CODE ###

N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)
### BUGGY CODE ###

n=int(input())
arr=[int(i) for i in input().split()]
ans=1
for i in arr:
  ans*=i
if ans<=1000000000000000000:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

n=int(input())
arr=[int(i) for i in input().split()]
ans=1
if 0 in arr:
    print(0)
else:
    for i in arr:
        ans=ans*i
        boo=True
        if ans>1000000000000000000:
            print(-1)
            boo=False
            break
    if boo:
        print(ans)
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

# n, k = map(int, input().split())
# a = list(map(int, input().split()))
s = input()
q = int(input())
rev = False
for i in range(q):
    que = input()
    if que[0] == '1':
        rev = not rev
    else:
        que = list(que.split())
        if (int(que[1])==1 and not rev) or (int(que[1])==2 and rev):
            s = que[2] + s
        else:
            s = s + que[2]

if rev: ans = ''.join(list(reversed(s)))
else: ans = s
print(ans)


### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

# n, k = map(int, input().split())
# a = list(map(int, input().split()))
s = deque(input())
q = int(input())
rev = False
for i in range(q):
    que = input()
    if que[0] == '1':
        rev = not rev
    else:
        que = list(que.split())
        if (int(que[1])==1 and not rev) or (int(que[1])==2 and rev):
            s.appendleft(que[2])
        else:
            s.append(que[2])

if rev: ans = ''.join(reversed(s))
else: ans = ''.join(s)
print(ans)
### BUGGY CODE ###

from collections import deque
s = list(input())
queue = deque()
res = 0
count = 0
for c in s:
    queue.append(c)
    count += 1
    if count >= 2:
        if "0" == queue[-1] and "1" == list(queue)[-2] or "0" == queue[-2] and "1" == list(queue)[-1]:
             res += 2
             count -= 2 
             queue.pop()
             queue.pop()
print(res)

### FIXED CODE ###

from collections import deque
s = list(input())
queue = deque()
res = 0
count = 0
for c in s:
    queue.append(c)
    count += 1
    if count >= 2:
        if "0" == queue[-1] and "1" == queue[-2] or "0" == queue[-2] and "1" == queue[-1]:
             res += 2
             count -= 2
             queue.pop()
             queue.pop()
print(res)
### BUGGY CODE ###

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

N = int(input())

ans = int(((1 + N)*N/2) - N)


for i in range(1, N):
    if i < N%i:
        ans -= i
        ans += N%i

print(ans)


### FIXED CODE ###

N = int(input())

ans = (N * (N-1) // 2)
print(ans)
### BUGGY CODE ###

num = input()
list = list(map(int,input().split()))
flg  = False
for i in list:
  if list.count(i) >= 2:
  	flg = True
print("NO") if flg else print("YES")

### FIXED CODE ###

num = input()
list = list(map(int,input().split()))
list2 = set(list) 
print("YES") if len(list) == len(list2) else print("NO")
### BUGGY CODE ###

card_count, rewrite_count = map(int, input().split(" "))
cards = list(map(int, input().split(" ")))

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    for _ in range(stock_count):
        minimum_index = cards.index(min(cards))

        if rewrite_number <= cards[minimum_index]:
            break

        cards[minimum_index] = rewrite_number

print(sum(cards))


### FIXED CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

print(total)
### BUGGY CODE ###

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

arr = []
R = len(list(filter(lambda x:x == 'R', s)))
G = len(list(filter(lambda x:x == 'G', s)))
B = len(list(filter(lambda x:x == 'B', s)))
tot = R*G*B

for i in range(n):
  for j in range(i+1, n):
    k = 2*j-i
    if k >= n:
      continue
    if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
      tot -= 1

print(tot)


### FIXED CODE ###

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

arr = []
R = len(list(filter(lambda x:x == 'R', s)))
G = len(list(filter(lambda x:x == 'G', s)))
B = len(list(filter(lambda x:x == 'B', s)))
tot = R*G*B

for i in range(n):
  for j in range(i+1, n):
    k = 2*j-i
    if k >= n:
      continue
    if (s[i] != s[j]) and (s[i] != s[k]) and (s[j] != s[k]):
      tot -= 1

print(tot)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

def dfs(x, y, cnt):
    flag = [1] * 4
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            flag[i] = 0
            d[nx][ny] = cnt
            dfs(nx, ny, cnt)
    for i in range(4):
        if flag[i]:
            nx = x + tx[i] * 2
            ny = y + ty[i] * 2
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt + 1:
                d[nx][ny] = cnt + 1
                dfs(nx, ny, cnt + 1)
    for i in range(4):
        if flag[i] & flag[(i+1) % 4]:
            for j in range(1, 3):
                for k in range(1, 3):
                    nx = x + tx[i] * j + tx[(i+1) % 4] * k
                    ny = y + ty[i] * j + ty[(i+1) % 4] * k
                    if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt + 1:
                        d[nx][ny] = cnt + 1
                        dfs(nx, ny, cnt + 1)

d[C[0]-1][C[1]-1] = 0
dfs(C[0]-1, C[1]-1, 0)

if d[D[0]-1][D[1]-1] == INF:
    print(-1)
else:
    print(d[D[0]-1][D[1]-1])

### FIXED CODE ###

from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

Q = deque()
Q.append([C[0]-1, C[1]-1, 0])

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    if x == D[0]-1 and y == D[1]-1:
        print(cnt)
        sys.exit()
    
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            Q.appendleft([nx, ny, cnt])
    
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt+1:
            d[nx][ny] = cnt+1
            Q.append([nx, ny, cnt+1])

print(-1)
### BUGGY CODE ###

def p_j():
    def recursion_j(i, j, k):
        if dp[i][j][k] > 0:
            return dp[i][j][k]
        if i == j == k == 0:
            return 0

        res = 0
        if i > 0:
            res += recursion_j(i - 1, j, k) * i
        if j > 0:
            res += recursion_j(i + 1, j - 1, k) * j
        if k > 0:
            res += recursion_j(i, j + 1, k - 1) * k
        res += n
        res *= 1 / (i + j + k)
        dp[i][j][k] = res
        return res

    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(c[0], c[1], c[2]))
    
p_j()

### FIXED CODE ###

def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for k in range(c3 + 1):
        for j in range(c3 + c2 + 1 - k):
            for i in range(n + 1 - k - j):
                if i + j + k == 0:
                    continue
                res = n
                if i > 0:
                    res += i * dp[i - 1][j][k]
                if j > 0:
                    res += j * dp[i + 1][j - 1][k]
                if k > 0:
                    res += k * dp[i][j + 1][k - 1]
                res /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()
### BUGGY CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))

nums = [0]*n
for i in range(n): nums[i] = sum(range(1, p[i]+1))/p[i]

ans = sum(nums[:k])
t = sum(nums[:k])
for i in range(k,n):
  t += nums[i] - nums[i-k]
  if ans < t: ans = t
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))

# 値ごとの期待値を取得
s = [0]*n
for i in range(n):
  s[i] = (p[i]+1)/2

# 期待値を累積していく
p = [0]*(n+1)
for i in range(1, n+1):
  p[i] = p[i-1] + s[i-1]

# 下記の方法で隣接する期待値合計を取得し、比較を行う。
# 隣接する期待値の合計　= 対象とする範囲の最大累積和　- 対象外範囲の最大累積和
ans = 0
for i in range(n-k+1):
  ans = max(ans, p[i+k] - p[i])

print(ans)