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

def main():
    from functools import reduce
    from fractions import gcd
    from collections import deque

    n, *a = map(int, open(0).read().split())
    p = deque(a)
    edge1 = reduce(gcd, a[1:])
    edge2 = reduce(gcd, a[:-1])
    full = reduce(gcd, a)
    ans = max([edge1, edge2, full])
    gl = p.pop()
    tmp = gl
    for i in range(n - 2):
        tmp2 = p.pop()
        gr = reduce(gcd, p)
        gl = gcd(gl, tmp)
        tmp = tmp2
        g = gcd(gl, gr)
        ans = max(ans, g)
        
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = [0] + a + [0]
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


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

import numpy as np
n=int(input())
a_=list(map(int,input().split()))
a=np.array(a_)
#print(a)
s=min(a)
for i in range(s,0,-1):
  if np.all(a%i==0):
    print(i)
    exit()

### FIXED CODE ###


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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
m=a_[0]
for i in range(n):
  m=gcd(m,a_[i])
  
print(m)
### BUGGY CODE ###

S = input()
Q = int(input())


condition = [list(map(str, input().split())) for i in range(Q)]

front = True

for i in condition:

    if i[0] == '1':
        front = not front

    elif i[0] == '2':
        if i[1] == '1':
            if front:
                S = i[2] + S
            else:
                S = S + i[2]
        elif i[1] == '2':
            if front:
                S = S + i[2]
            else:
                S = i[2] + S

if not front:
    S = ''.join(list(reversed(S)))

print(S)


### FIXED CODE ###

from collections import deque
d = deque()

S = input()
Q = int(input())
d.extend(S)




front = True

for i in range(Q):
    inp = input().split()
    if inp[0] == '1':
        front = not front
    else:
        F = int(inp[1])
        C = inp[2]
        if F == 1:
            if front:
                d.appendleft(C)
            else:
                d.append(C)
        elif F == 2:
            if front:
                d.append(C)
            else:
                d.appendleft(C)

if not front:
    d.reverse()

d_list = list(d)
str = "".join(d_list)

print(str)
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
connect=[[0]*N for i in range(N)]

for i in range(M):
    A,B=map(int,input().split())
    connect[A-1][B-1]=H[B-1]
    connect[B-1][A-1]=H[A-1]

count=0
for i in range(N):
    if H[i]>max(connect[i]) or max(connect[i])==0:
        count+=1
# for i in range(N):
#     print(connect[i])
print(count)

### FIXED CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
connect=[[] for i in range(N)]

for i in range(M):
    A,B=map(int,input().split())
    connect[A-1].append(H[B-1])
    connect[B-1].append(H[A-1])

count=0
for i in range(N):
    if not connect[i]:
        count+=1
    elif H[i]>max(connect[i]):
        count+=1
# for i in range(N):
#     print(connect[i])
print(count)
### BUGGY CODE ###

from sys import stdin
input=stdin.readline
a=1
n=int(input())
ar=list(map(int,input().strip().split()))
for i in ar:
    a*=i
if(a>1000000000000000000):
    print("-1")
else:
    print(a)

### FIXED CODE ###

from sys import stdin
input=stdin.readline
a=1
ok=0
n=int(input())
ar=list(map(int,input().strip().split()))
ar.sort()
for i in ar:
    a*=i
    if(i==0):
        ok=1
        print(0)
        break
    if(a>1000000000000000000):
        ok=1
        print(-1)
        break
    # print(i)
if(ok==0):
    print(a)
### BUGGY CODE ###

def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


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

import math

N = int(input())
ans = 0
print(int(sum([math.floor(N / (i+1)) * (math.floor(N / (i+1)) + 1) * (i+1) / 2  for i in range(N)])))


### FIXED CODE ###

N = int(input())
ans = 0
 
for i in range(1, N+1):
  Y = N // i
  ans += Y * (Y+1) * i / 2
  
print(int(ans))
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

ch-=1
cw-=1
dh-=1
dw-=1

S=[]
for _ in range(h):
  s=input()
  sl=[]
  for i in range(w):
    sl.append(s[i])
  S.append(sl)

def isable(X):
  xh,xw=X[0],X[1]
  if 0<=xh<=h-1 and 0<=xw<=w-1 and S[xh][xw]=='.':
    return True
  else:
    return False

def stepA(X):
  xh,xw=X[0],X[1]
  A=[]
  for p,q in [(-1,0),(0,1),(1,0),(0,-1)]:
    if isable([xh+p,xw+q]):
      A.append([xh+p,xw+q])
  return A
    
def stepB(X):
  xh,xw=X[0],X[1]
  B=[]
  for i in range(-2,3):
    for j in range(-2,3):
      if i==0 and j==0:
        continue
      if isable([xh+i,xw+j]):
        B.append([xh+i,xw+j])
  return B

Q=deque()
Q.appendleft((ch,cw))
cost=[[float('inf') for i in range(w)] for j in range(h)]
cost[ch][cw]=0

while Q:
  ph,pw=Q.popleft()
  for v in stepA([ph,pw]):
    ah,aw=v[0],v[1]
    if isable([ah,aw]):
      if cost[ah][aw]>cost[ph][pw]:
        cost[ah][aw]=cost[ph][pw]
        Q.appendleft([ah,aw])
  for bh,bw in stepB([ph,pw]):
    if isable([bh,bw]):
      if cost[bh][bw]>cost[ph][pw]+1:
        cost[bh][bw]=cost[ph][pw]+1
        Q.append([bh,bw])

if cost[dh][dw]==float('inf'):
  print(-1)
else:
  print(cost[dh][dw])

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

ch-=1
cw-=1
dh-=1
dw-=1

S=[]
for _ in range(h):
  s=input()
  sl=[]
  for i in range(w):
    sl.append(s[i])
  S.append(sl)

def isable(X):
  xh,xw=X[0],X[1]
  if 0<=xh<=h-1 and 0<=xw<=w-1 and S[xh][xw]=='.':
    return True
  else:
    return False

def stepA(X):
  xh,xw=X[0],X[1]
  A=[]
  for p,q in [(-1,0),(0,1),(1,0),(0,-1)]:
    if isable([xh+p,xw+q]):
      A.append([xh+p,xw+q])
  return A
    
def stepB(X):
  xh,xw=X[0],X[1]
  B=[]
  for i in range(-2,3):
    for j in range(-2,3):
      if i==0 and j==0:
        continue
      if isable([xh+i,xw+j]):
        B.append([xh+i,xw+j])
  return B

Q=deque()
Q.appendleft((ch,cw))
cost=[[float('inf') for i in range(w)] for j in range(h)]
cost[ch][cw]=0

while Q:
  ph,pw=Q.popleft()
  for v in stepA([ph,pw]):
    ah,aw=v[0],v[1]
    if isable([ah,aw]):
      if cost[ah][aw]>cost[ph][pw]:
        cost[ah][aw]=cost[ph][pw]
        Q.appendleft([ah,aw])
  for bh,bw in stepB([ph,pw]):
    if isable([bh,bw]):
      if cost[bh][bw]>cost[ph][pw]+1:
        cost[bh][bw]=cost[ph][pw]+1
        Q.append([bh,bw])

if cost[dh][dw]==float('inf'):
  print(-1)
else:
  print(cost[dh][dw])
### BUGGY CODE ###

#Coding:Utf-8

N,Q=input().split()
S=list(map(str,input()))
b=[]
c=[]
for i in range(int(Q)):
  a=list(map(int, input().split()))
  b.extend((a))
for j in range(0,int(Q)*2,2):
  count=0
  for l in range(b[j],b[j+1]):
    if S[l-1]=="A" and S[l]=="C":
      count+=1
  else:
    print(count)

### FIXED CODE ###

#Coding:Utf-8

N,Q=input().split()
S=input()
S= S.replace("AC","Ac")


def judge(x):
  if x=="c":
    return 1
  else:
    return 0


t=[]
t.append(0)

for i in range(1,int(N)):
  t.append(t[i-1]+judge(S[i]))

for j in range(int(Q)):
  a,b=list(map(int, input().split()))
  print(t[b-1]-t[a-1])
### BUGGY CODE ###

h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)


### FIXED CODE ###

h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

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

# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

from collections import deque

field = [[None] * W for _ in range(H)]
q = deque([])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            field[i][j] = 0
            q.append((i, j, 0))
            cnt += 1

tblr = ((-1, 0), (1, 0), (0, -1), (0, 1))
while cnt < H * W:
    y, x, d = q.popleft()
    for dy, dx in tblr:
        if y + dy < 0: continue
        if x + dx < 0: continue
        if y + dy >= H: continue
        if x + dx >= W: continue
        if field[y + dy][x + dx] != None: continue
        #
        field[y + dy][x + dx] = d + 1
        q.append((y + dy, x + dx, d + 1))
        cnt += 1

print(max([max(field[i]) for i in range(H)]))


### FIXED CODE ###

# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

from collections import deque

field = [[None] * W for _ in range(H)]
q = deque([])
cnt = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            field[i][j] = 0
            q.append((i, j, 0))
            cnt += 1

tblr = ((-1, 0), (1, 0), (0, -1), (0, 1))
while cnt < H * W:
    y, x, d = q.popleft()
    for dy, dx in tblr:
        if y + dy < 0: continue
        if x + dx < 0: continue
        if y + dy >= H: continue
        if x + dx >= W: continue
        if field[y + dy][x + dx] != None: continue
        #
        field[y + dy][x + dx] = d + 1
        q.append((y + dy, x + dx, d + 1))
        cnt += 1

print(max([max(field[i]) for i in range(H)]))
### BUGGY CODE ###

h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
res_array = []
res = 0
moving = [[0, 1], [1, 0]]


def recursive(mark, row, point, origin_x, origin_y):
    if row == 0 and row == h and w == 0 and w == row:
        return
    for x, y in moving:
        if s_array[row][point] != s_array[row + x][point + y] and s_array[row + x][point + y] != "+":
            tmp = [[origin_x, origin_y], [row + x, point + y]]
            if tmp not in res_array and mark != s_array[row + x][point + y]:
                res_array.append(tmp)
            recursive(mark, row+x, point+y, origin_x, origin_y)
    else:
        return


for row in range(1, h + 1):
    for point in range(1, w + 1):
        recursive(s_array[row][point], row, point, row, point)

print(len(res_array))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)


h, w = map(int, input().split())
s_array = ["+" * (w + 2)]
for i in range(h):
    s_array.append("+" + input() + "+")
else:
    s_array.append("+" * (w + 2))
moving = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit = [[False for x in range(w+2)] for x in range(h+2)]


def recursive(mark_point, mark_sharp, row, point):
    # 訪問済みならreturn
    if visit[row][point]:
        return mark_point, mark_sharp
    else:
        visit[row][point] = True

    for x, y in moving:
        # 範囲外かどうかと連結かどうか
        if s_array[row + x][point + y] != "+" and s_array[row + x][point + y] != s_array[row][point]:
            if visit[row+x][point+y]:
                continue
            # 移動先のマークの確認
            if s_array[row + x][point + y] == "#":
                mark_sharp += 1
            else:
                mark_point += 1
            mark_point, mark_sharp = recursive(mark_point, mark_sharp, row + x, point + y)
    else:
        return mark_point, mark_sharp


res = 0
for row in range(1, h + 1):
    for point in range(1, w + 1):
        m, n = recursive(s_array[row][point].count("."), s_array[row][point].count("#"), row, point)
        res += m*n
print(res)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc043/tasks/agc043_a

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    h, w = input_int_list()
    grid = []
    grid.append(["#"] * (w + 2))
    for _ in range(h):
        grid.append(["#"] + list(input()) + ["#"])
    grid.append(["#"] * (w + 2))
    ans = set()

    def search(x, y, cnt):
        if grid[y][x] == "#":
            cnt += 1

        if y == h and x == w:
            ans.add(cnt)
            return
        else:
            if y < h:
                search(x, y + 1, cnt)
            if x < w:
                search(x + 1, y, cnt)
    search(1, 1, 0)
    print(min(ans))
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
H,W = map(int,readline().split())
S = ''.join(read().decode().split())
 
INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]
 
print(min(dp[-1]))
### BUGGY CODE ###

ans=0

def br(s):
  global ans
  ns=[]
  fl=True
  i=0
  while i <len(s):
    if s[i:i+2]==["0","1"] or s[i:i+2]==["1","0"]:
      ans+=2
      i+=1
      fl=False
    else:
      ns.append(s[i])
    i+=1

  if fl or len(ns)==0:
    return 0
  else:
    br(ns)

br(list(input()))
print(ans)

### FIXED CODE ###

s=list(input())
print(len(s)-abs(s.count("0")-s.count("1")))
### BUGGY CODE ###

def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

dp = makelist(n+1,n+1,n*X+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j*k > 0 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
ans = 0
for k in range(1,n+1):
    ans += dp[n][k][k*a]
print(ans)

### FIXED CODE ###

def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

dp = makelist(n+1,n+1,n*a+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*a+1):
            if j*k > 0 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
ans = 0
for k in range(1,n+1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

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

table = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    table[a-1][b-1] += 1

s = [[0] for i in range(n)]

for i in range(n):
    for j in range(n):
        s[i].append(s[i][-1]+table[i][j])

for _ in range(q):
    i, j = map(int, input().split())
    tmp = 0
    if i == 1:
        for k in range(i-1, j):
            tmp += s[k][j]
    else:
        for k in range(i-1, j):
            tmp += s[k][j] - s[k][i-1]
    print(tmp)



### FIXED CODE ###

n, m, q = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(m)]
y = [tuple(map(int, input().split())) for _ in range(q)]

table = [[0]*n for _ in range(n)]

for i, j in x:
    table[i-1][j-1] += 1

for i in range(n):
    for j in range(1, n):
        table[i][j] += table[i][j-1]

for i in range(n-1, 0, -1):
    for j in range(n):
        table[i-1][j] += table[i][j]

for i, j in y:
    print(table[i-1][j-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    S = [input() for _ in range(N)]

    T = sorted(list(set(S)))
    C = []
    for i in T:
        C.append(S.count(i))

    for i in range(len(C)):
        if C[i] == max(C):
            print(T[i])

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    S = [input() for _ in range(N)]

    T = sorted((set(S)))
    l = len(T)

    D = {}
    for i in range(l):
        D[T[i]] = 0
    for i in range(N):
        D[S[i]] += 1

    m = max(D.values())
    for i in range(l):
        if D[T[i]] == m:
            print(T[i])


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

from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    if a in C:
        continue

    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
L %= mod

ans = 0
for a in A:
    ans += L * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

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

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0 for i in range(N)]

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)

### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(N-1)]
operations = [list(map(int, input().split())) for _ in range(Q)]

edge_map = [[] for i in range(N)]

for edge in edges:
    a = edge[0]
    b = edge[1]
    edge_map[a-1].append(b-1)
    edge_map[b-1].append(a-1)


counters = [0]*N

for operation in operations:
    p = operation[0]
    x = operation[1]
    counters[p-1] += x


res_list = [counters[i] for i in range(N)]
calculated = [False for i in range(N)]

target = [0]
while len(target) > 0:
    t = target.pop()
    calculated[t] = True
    for child in edge_map[t]:
        if calculated[child]:
            continue
        target.append(child)
        res_list[child] += res_list[t]

print(*res_list)
### BUGGY CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

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

count = Counter(A)

for num in A:
    ans = 0
    for key, value in count.items():
        if key != num:
            ans += value*(value-1)//2
        else:
            ans += (value-1)*(value-2)//2
    print(ans)


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

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

count = Counter(A)
sm = {}
sm2 = {}
for key, value in count.items():
    sm[key] = value*(value-1)//2
    sm2[key] = (value-1)*(value-2)//2
total = sum(sm.values())

for num in A:
    print(total - sm[num] + sm2[num])
### BUGGY CODE ###

N,K = map(int,input().split())
dice_list = [int(i) for i in input().split()]
wa_list = [0]
for dice in dice_list :
    prob = 0
    for i in range(dice) :
        prob += (i+1) * (1/(dice))
    wa_list.append(wa_list[-1] + prob)

max_p = -1
for i in range(N-K+1) :
    p = wa_list[i+K] - wa_list[i]
    if (max_p < p) :
        max_p = p

print(max_p)





### FIXED CODE ###

N,K = map(int,input().split())
dice_list = [int(i) for i in input().split()]
wa_list = [0]
for dice in dice_list :
    # prob = 0
    # for i in range(dice) :
    #     prob += (i+1) * (1/(dice))
    prob = (1+dice) / 2
    wa_list.append(wa_list[-1] + prob)

max_p = -1
for i in range(N-K+1) :
    p = wa_list[i+K] - wa_list[i]
    if (max_p < p) :
        max_p = p

print(max_p)