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

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
edges = ABC[:]

# 無効グラフなので双方向にする
graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]


shortest = [[0] * (N+1)]
for i in range(1, N+1):
    shortest.append(dijkstra(graph, i))
    
#print(shortest)

import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import itertools
line = R_LIST
for l in itertools.permutations(line):
    #print(l)
    tmp_len = 0
    for a,b in zip(l[:-1], l[1:]):
        tmp_len += shortest[a][b]

    #print(tmp_len)
    ans = min(ans, tmp_len)
print(ans)

### FIXED CODE ###

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))
### BUGGY CODE ###

#A,B,C,D=map(int,input().split(" "))

N=int(input())

S=[]
ans=0

for i in range(N):
  a=input()
  if a in S:
    a=0
  else:
    S.append(a)
    ans += 1
  
print(ans)

### FIXED CODE ###

#A,B,C,D=map(int,input().split(" "))

N=int(input())

S=[]
ans=0

for i in range(N):
  S.append(input())

ans = len(list(set(S)))

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

def main():
    import sys
    input = sys.stdin.buffer.readline
    
    r, c, k = map(int, input().split())
    tizu = [[0 for _ in range(c)] for _ in range(r)]
    for _ in range(k):
        rr, cc, v = map(int, input().split())
        tizu[rr - 1][cc - 1] = v
        
    dp = [[0, 0, 0, 0] for _ in range(c)]
    dp[0][1] = tizu[0][0]
    
    for i in range(r):
        for j in range(c):
            if i != 0:
                tmp = max(dp[j])
                dp[j][0] = tmp
                dp[j][1] = tmp + tizu[i][j]
                dp[j][2] = 0
                dp[j][3] = 0
            if j != 0:
                dp[j][0] = max(dp[j][0], dp[j - 1][0])
                dp[j][1] = max(dp[j][1], dp[j - 1][1], dp[j - 1][0] + tizu[i][j])
                dp[j][2] = max(dp[j - 1][2], dp[j - 1][1] + tizu[i][j])
                dp[j][3] = max(dp[j - 1][3], dp[j - 1][2] + tizu[i][j])
    print(max(dp[-1]))
    
main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    
    r, c, k = map(int, input().split())
    tizu = [0 for _ in range(r * c)]
    for _ in range(k):
        rr, cc, v = map(int, input().split())
        tizu[(rr - 1) * c + (cc - 1)] = v
        
    dp = [[0, 0, 0, 0] for _ in range(c)]
    dp[0][1] = tizu[0]
    
    for i in range(r):
        for j in range(c):
            v = tizu[i * c + j]
            if v:
                if i != 0:
                    tmp = max(dp[j])
                    dp[j] = [tmp, tmp + v, 0, 0]
                if j != 0:
                    tmp0 = dp[j - 1][0]
                    tmp1 = dp[j - 1][1]
                    tmp2 = dp[j - 1][2]
                    lst = [max(dp[j][0], tmp0), max(dp[j][1], tmp1, tmp0 + v), max(tmp2, tmp1 + v), max(dp[j - 1][3], tmp2 + v)]
                    dp[j] = lst
            else:
                if i != 0:
                    tmp = max(dp[j])
                    dp[j] = [tmp, 0, 0, 0]
                if j != 0:
                    lst = [max(dp[j][0], dp[j-1][0]), dp[j-1][1], dp[j-1][2], dp[j - 1][3]]
                    dp[j] = lst
    print(max(dp[-1]))
    
main()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys

sys.setrecursionlimit(int(1e5))


def lcs(w1, w2):
    m, n = len(w1), len(w2)
    dp = tuple([0] * (n + 1) for _ in range(m + 1))
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def lcs_recursive(w1, w2, m, n):
    if m == 0 or n == 0:
        return 0
    elif w1[m - 1] == w2[n - 1]:
        return 1 + lcs_recursive(w1, w2, m - 1, n - 1)
    else:
        return max(lcs_recursive(w1, w2, m, n - 1), lcs_recursive(w1, w2, m - 1, n))


def solve():
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])
    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num

    for pair in zip(word_list[::2], word_list[1::2]):
        cw1, cw2 = map(lambda x: x.strip(), pair)
        print(lcs(cw1, cw2))
        # l1, l2 = len(cw1), len(cw2)
        # print(lcs_recursive(cw1, cw2, l1, l2))

    return None


if __name__ == '__main__':
    solve()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n in range(1, N):
    l = max(0, n - K)
    dp[n] = min(abs(A[n] - a) + d for a, d in zip(A[l : n], dp[l : n]))

print(dp[-1])


### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

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

n=int(input())

li2=[input() for i in range(n)]
xl = []
for i in range(n):
    xl.append( [int(x.strip()) for x in li2[i].split()])

t = []
t_ = []
for i in range(n):
    t.append(sum(xl[i]))
    t_.append(sum(xl[i]))

ans = 0
use = []
used = list(range(n))
t_.sort()

for i in range(n):
    a = t_[0]
    ind = t.index(a)
    ok = 1


    for j in range(ans):
        #print(xl[used[ind]][0] - xl[used[ind]][1])
        #print(use[j][0] + use[j][1])

        if xl[used[ind]][0] - xl[used[ind]][1] < use[j][0] + use[j][1]:
            #print("b")
            ok = 0
            break


    if ok == 1:
        use.append(xl[ind])
        ans+= 1

    t.pop(ind)
    used.pop(ind)
    t_.pop(0)

print(ans)


### FIXED CODE ###

N = int(input())
l = []

for i in range(N):
    a, b = map(int, input().split())
    l.append((a-b,a+b))

l = sorted(l,key=lambda x:x[1])

start = l[0][1]
ans = 1
for i in range(1,N):
    if start <= l[i][0]:
        start = l[i][1]
        ans += 1

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

def cmb(n, r, p):
	if (r<0) or (n<r):
		return 0
	r=min(r, n-r)
	return fact[n]*factinv[r]*factinv[n-r]%p

p=10**9+7
N=10**6
fact=[1,1]
factinv=[1,1]
inv=[0,1]

for i in range(2, N+1):
	fact.append((fact[-1]*i)%p)
	inv.append((-inv[p%i]*(p//i)%p))
	factinv.append((factinv[-1]*inv[-1])%p)


N=int(input())
A=list(map(int,input().split()))
index=[[] for _ in range(N+1)]

for i in range(N+1):
    index[A[i]].append(i)

for i in range(1,N+1):
    if len(index[i])==2:
        dup=i

mod=10**9+7
n=index[dup][0]
m=N-index[dup][1]
l=n+m
for k in range(1,N+2):
    if k==1:
        print(N)
        continue   
    
    ans=cmb(N+1,k,mod)
    if l>=k-1:
        for i in range(k):
            ans-=cmb(n,i,mod)*cmb(m,k-1-i,mod)
    print(ans)

### FIXED CODE ###

def cmb(n, r, p):
	if (r<0) or (n<r):
		return 0
	r=min(r, n-r)
	return fact[n]*factinv[r]*factinv[n-r]%p

p=10**9+7
N=10**6
fact=[1,1]
factinv=[1,1]
inv=[0,1]

for i in range(2, N+1):
	fact.append((fact[-1]*i)%p)
	inv.append((-inv[p%i]*(p//i)%p))
	factinv.append((factinv[-1]*inv[-1])%p)


N=int(input())
A=list(map(int,input().split()))
index=[-1]*N
for i,a in enumerate(A):
    if index[a-1]!=-1:
        dup_first,dup_second=index[a-1],i
        break
    index[a-1]=i

mod=10**9+7
n=dup_first
m=N-dup_second
l=n+m
for k in range(1,N+2):
    if k==1:
        print(N)
        continue
    ans=(cmb(N+1,k,mod)-cmb(l,k-1,mod))%mod
    print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
# 解説読んだ後
def maxspeed(left,right,t,vmax):
    if t<=left:
        return vmax+(left-t)
    elif left< t < right:
        return vmax
    else:
        return vmax+t-right
funcs=[]
funcs.append((0,0,0))
left=0
for i in range(N):
    funcs.append((left,left+T[i],V[i]))
    left+=T[i]
funcs.append((left,left,0))
dist=0.0
speed=0
for t in np.arange(0.0,left+0.5,0.5):
    speed2=min(maxspeed(pm[0],pm[1],t,pm[2]) for pm in funcs)
    if 0< t:
        dist+=(speed+speed2)*0.5/2
    speed=speed2
print(dist)

### FIXED CODE ###

N=int(input().strip())
T=list(map(int,input().split()))
V=list(map(int,input().split()))
vtmax=[0]
tmp=0
Tsum=sum(T)
for t,v in zip(T,V):
    vtmax[-1]=min(tmp,v) #境界は小さい方が制約
    vtmax+=[v]*(t*2)
    tmp=v
vtmax[-1]=0

for i in range(1,2*Tsum):
    vtmax[i]=min(vtmax[i],vtmax[i-1]+0.5)
for i in range(2*Tsum-1,0,-1):
    vtmax[i]=min(vtmax[i],vtmax[i+1]+0.5)
area=0
for i,vt in enumerate(vtmax):
    if i==0:continue
    area+=0.5*(vt+vtmax[i-1])/2
print(area)
### BUGGY CODE ###

import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = 1
    k = 1
    while k <= K:
        if A[i] in pas:
            rps = np.where(pas==(A[i]))[0] # roop start index
            ans = A[i]
            break
        pas[k] = A[i]
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))
main()

### FIXED CODE ###

import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()
### BUGGY CODE ###

import itertools 
n,k=map(int,input().split())
H=[int(input()) for i in range(n)]
Hn=list(itertools.combinations(H,k))
print(min([max(list(i))-min(list(i)) for i in Hn]))


### FIXED CODE ###

n,k=map(int,input().split())
h=sorted([int(input()) for i in range(n)])
print(min([h[i+k-1]-h[i] for i in range(n-k+1)]))
### BUGGY CODE ###

a,aa=map(int,input().split())
b=list(map(int,input().split()))
c=[0 for i in range(a)]
c[0]=0
for i in range(1,a):
  c[i] = min(c[j] + abs(b[i] - b[j]) for j in range(max(0,i-aa),i))
print(c[-1])

### FIXED CODE ###

def solve():
  a,aa=map(int,input().split())
  b=list(map(int,input().split()))
  c=[0]*a
  c[0]=0
  for i in range(1,a):
    c[i] = min(c[j] + abs(b[i] - b[j]) for j in range(max(0,i-aa),i))
  print(c[-1])
  
solve()
### BUGGY CODE ###

from sys import stdin
n = stdin.readline().rstrip()
a = [int(x) for x in stdin.readline().rstrip().split()]
b = 0

print(a)

while True:
   if all([x % 2 == 0 for x in a]):
      a = [x/2 for x in a]
      b += 1
   else:
      break

print(b)

### FIXED CODE ###

from sys import stdin
a = [int(x) for x in list(stdin.readline().rstrip())]
y = 0

for x in a:
    if x == 1:
        y += 1

print(y)
### BUGGY CODE ###

s = input().rstrip()
N = int(s)

ans = 0

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if str(i)[-1] == str(j)[0] and str(i)[0] == str(j)[-1]:
            ans = ans + 1

print(ans)


### FIXED CODE ###

s = input().rstrip()
N = int(s)

ans = 0
i = 1
order = len(str(N))

params = {}

for i in range(1, N + 1):
    Akey = str(i)[-1] + str(i)[0] 
    if params.get(Akey) is not None:
        params[Akey] = params[Akey] + 1
    else:
        params[Akey] = 1

for i in range(1, N + 1):
    Bkey = str(i)[0] + str(i)[-1] 
    count = params.get(Bkey)
    if count is not None:
        ans =  ans + count;

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

# coding: utf-8
num = int(input())


def make_sum(ind):
    return sum(range(1, ind + 1))

ans = 0

if num == 1:
    print(1)
else:
    while True:
        ans += 1
        if make_sum(ans) < num <= make_sum(ans + 1):
            break

    print(ans + 1)

### FIXED CODE ###

# coding: utf-8
num = int(input())


# def make_sum(ind):
#     return sum(range(1, ind + 1))

ans = 0
sum_num = 0

if num == 1:
    print(1)
else:
    while True:
        ans += 1
        sum_num += ans
        if sum_num < num <= (sum_num + ans + 1):
            break

    print(ans + 1)
### BUGGY CODE ###

n = int(input())
n_list = [int(i) for i in input().split()]
ans = 0
mod = 10 ** 9 + 7
num_list = [n % mod for n in n_list]
a_list = []

while len(num_list) > 1:
    x = num_list[0]
    num_list.remove(x)
    a_list.append((x * (sum(num_list) % mod)) % mod)

ans = sum(a_list) % mod

print (ans)

### FIXED CODE ###

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

s = sum(a**2 for a in n_list)
ans = sum(n_list) ** 2 - s

print((ans//2)%(10**9+7))
### BUGGY CODE ###

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

su=[]
for i in s:
    su.append(sorted(list(i)))


count=0
while len(su)>0:
  j=su[0]
  del su[0]
  c=su.count(j)+1
  count+=c*(c-1)/2
  su=[i for i in su if i!=j]
  
print(int(count))

### FIXED CODE ###

import collections
N=int(input())
su=["".join(sorted(list(input()))) for _ in range(N)]

C=list(collections.Counter(su).values())

ans=0
for i in C:
  if i>1:
    ans+=i*(i-1)//2

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

n = int(input())
s = str(input())
r, g, b = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r*g*b


def rgb(k, i):
    se = set()
    se.add(s[i])
    se.add(s[i+k])
    se.add(s[i+2*k])
    if len(se) == 3:
        return True
    return False


for k in range(1, n//2+1):
    for i in range(n):
        if i+2*k >= n:
            break
        if rgb(k, i):
            ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
s = str(input())
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b

for k in range(1, n//2+1):
    for i in range(n):
        if i+2*k >= n:
            break
        if s[i] != s[i+k] and s[i] != s[i+2*k] and s[i+k] != s[i+2*k]:
            ans -= 1
print(ans)
### BUGGY CODE ###


INF = 10e5
n,k = list(map(int,input().split()))
h = list(map(int,input().split()))
dp = [INF for _ in range(n)]

dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    cost = []
    for j in range(1,k+1):
        if i >= j:
            cost.append(abs(h[i] - h[i-j]) + dp[i-j])
        else: break
    dp[i] = min(cost)

print(dp[n-1])


### FIXED CODE ###


INF = 2**31-1
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [INF for _ in range(n)]

dp[0] = 0

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

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

n,p=map(int,input().split())
s=input().rstrip()
ans=0
l=[]

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            ans+=i+1

else:
    for i in range(n):
        mod=int(s[-(i+1):])%p
        ans+=l.count(mod)
        l.append(mod)
        if mod==0:
            ans+=1

print(ans)

### FIXED CODE ###

n,p=map(int,input().split())
s=input().rstrip()
ans=0
l=[0]*p
a=[0,1,2,3,4,5,6,7,8,9]
c=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            ans+=i+1
else:
    for i in range(n):
        # mod=int(s[-(i+1):])%p
        mod=(c+a[int(s[-(i+1)])])%p
        ans+=l[mod]
        l[mod]+=1
        if mod==0:
            ans+=1
        c=mod
        
        for j in range(10):
            a[j]=a[j]*10%p
 
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
from collections import deque

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

n = i_i()
a = i_l()

d = deque([a[0]])

for x in a[1:]:
    d.append(x)
    d.reverse()

print(*d)


### FIXED CODE ###

from collections import deque

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

d = deque()
for i in range(n):
    if i % 2 != 0:
        d.append(a[i])
    else:
        d.appendleft(a[i])

if n % 2 == 0:
    print(*list(reversed(d)))
else:
    print(*d)
### BUGGY CODE ###

import re

s = input()
k = int(input())
ans = [min(s)]
i = 1
while True:
    if len(ans) == k:
        print(ans[-1])
        break
    else:
        base = ans[-1]
        sub = sorted(re.findall(base + '.', s))
        if len(sub) == 0:
            while True:
                if chr(ord(min(s))+1) in s:
                    ans.append(chr(ord(min(s))+1))
                    break
                elif i >= 100:
                    print('error')
                    break
                else:
                    i += 1

        else:
            ans.append(sub[0])


### FIXED CODE ###

import re

s = input()
k = int(input())
ans = [min(s)]
i = 1
while True:
    if len(ans) == k:
        print(ans[-1])
        break
    else:
        base = ans[-1]
        sub = sorted(re.findall(base + '.', s))
        if len(sub) == 0:
            while True:
                if chr(ord(min(s))+i) in s:
                    ans.append(chr(ord(min(s))+i))
                    break
                else:
                    i += 1

        else:
            ans.append(sub[0])
### BUGGY CODE ###

n = int(input())
frag = 10**18
a = list(map(int,input().split()))
  
ans = 1

for i in range(n):
  ans = ans * a[i]
    
if(ans > frag):
    ans = -1

print(ans)

### FIXED CODE ###

n = int( input() )
A = list( map( int,input().split() ) )
 
if 0 in A:
  print( 0 )
else:
  ret = 1
  for a in A:
    ret = ret * a
    if ret > 10 ** 18:
      ret = -1
      break
  print( ret )
### BUGGY CODE ###

(n, k) = [int(i) for i in input().split(" ")]
p = [int(i) for i in input().split(" ")]

maxNum = -1
maxIndex = [0, 0]
for i in range(n-k+1):
  s = sum(p[i:i+k])
  if s > maxNum:
    maxNum = s
    maxIndex = [i, i+k]

dices = p[maxIndex[0]:maxIndex[1]]
exs = 0
for dice in dices:
  exs += sum(list(range(1, dice+1))) / dice
print(exs)

### FIXED CODE ###

(n, k) = [int(i) for i in input().split(" ")]
p = [int(i) for i in input().split(" ")]

s = 0
sums = [0]
for i in p:
  	s += i
  	sums.append(s)

maxNum = -1
maxIndex = [0, 0]
for i in range(len(sums)-k):
  if sums[i+k] - sums[i] > maxNum:
    maxNum = sums[i+k] - sums[i]
    maxIndex = [i, i+k-1]

dices = p[maxIndex[0]:maxIndex[1]+1]
e = 0
for dice in dices:
  e += sum(list(range(1, dice+1))) / dice
print(e)