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

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[0]*N for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1][b-1] = G[b-1][a-1] = 1

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in range(N) :
        if G[now][i] == 1 :
            if col[i] == -1 :
                col[i] = (col[now] + 1)%2
                stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
else :
    mods = mod1 + mod0 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()

print(*ans)


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
else :
    mods = deque(mod1 + mod0 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()

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

if __name__=="__main__":
    n = int(input())
    As = list(map(int,input().split()))
    Non_dup_As = list(set(As))
    count = 0
    for a in Non_dup_As:
        count+=As.count(a)-1
    if(count % 2 == 0):
        print(len(As) - int(count))
    else:
        print(len(As) - int(count+1))


### FIXED CODE ###

if __name__=="__main__":
    n = int(input())
    As = list(map(int,input().split()))
    Non_dup_As = list(set(As))
    count = len(Non_dup_As)
    if(count % 2 == 0):
        print(count - 1)
    else:
        print(count)
### BUGGY CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Nlis[0] = 0

while len(Q) > 0 and N != 1:

    now = Q.pop(0)

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

for i in Nlis:
    print(i)


### FIXED CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Q_cnt = 0
Nlis[0] = 0

while len(Q) > Q_cnt and N != 1:

    now = Q[Q_cnt]
    Q_cnt += 1

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            #Ndic[nw[0]].remove([now,nw[1]])

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

N,M=map(int,input().split())
A=[[int(i) for i in input().split()] for _ in range(N)]
R=[0 for i in range(M)]
for i in range(N):
    R[A[i][0]-1]+=1
P=0
Q=0
S=set()
for i in range(N):
    if R[A[i][0]-1]>=P:
        P=R[A[i][0]-1]
        Q=A[i][0]
S.add(Q)
while(len(S)<M):
    Pd=0
    Qd=0
    R=[0 for i in range(M)]
    for i in range(N):
        for j in range(M):
            if not(set([A[i][j]]) <= S):
                R[A[i][j]-1]+=1
                break
    for j in range(M):
        if R[j]>=Pd:
            Pd=R[j]
            Qd=j+1
    if Pd<P:
        P=Pd
    S.add(Qd)
print(P)


### FIXED CODE ###

N,M=map(int,input().split())
A=[[int(i) for i in input().split()] for _ in range(N)]
R=[0 for i in range(M)]
for i in range(N):
    R[A[i][0]-1]+=1
P=0
Q=0
S=set()
for i in range(N):
    if R[A[i][0]-1]>=P:
        P=R[A[i][0]-1]
        Q=A[i][0]
S.add(Q)
while(len(S)<M):
    Pd=0
    Qd=0
    R=[0 for i in range(M)]
    for i in range(N):
        for j in range(M):
            if not(set([A[i][j]]) <= S):
                R[A[i][j]-1]+=1
                break
    for j in range(M):
        if R[j]>=Pd:
            Pd=R[j]
            Qd=j+1
    if Pd<P:
        P=Pd
    S.add(Qd)
print(P)
### BUGGY CODE ###

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

for i in range(N):
    cnt *= A[i]

if(cnt <= 1e18):
    print(cnt)
else:
    print(-1)


### FIXED CODE ###

import sys

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

for i in range(N):
    if(A[i] == 0):
        print(0)
        sys.exit()

for i in range(N):
    cnt *= A[i]
    if(cnt > 1e18):
        print(-1)
        sys.exit()

if(cnt <= 1e18):
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))
r = [1]
k += 1
now = 1
for i in range(n):
   now = a[now]
   if now in r: break
   r.append(now)
   if len(r) == k:
     print(now)
     exit()
I = r.index(now)
if I != 0: 
  k -= I
  r = r[I:]
print(r[-1] if k%len(r)==0 else r[k%len(r)-1])

### FIXED CODE ###

n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))

now = 1
check = [-1]*(n+1)

for i in range(k):
  if check[now] == -1:
    check[now] = i
    now = a[now]
  else:
    loop = i - check[now]
    afterloop = (k-(i-loop))%loop
    print(check.index((i-loop) + afterloop))
    exit()
print(now)
### BUGGY CODE ###

s = input()

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

for i in range(length):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                x = (j*10 + k)%13
                ans[i+1][x] = (ans[i+1][x] + ans[i][j]) % mod
        else:
            x = (j*10 + int(s[i])) % 13
            ans[i+1][x] = (ans[i+1][x] + ans[i][j]) % mod

print(ans[length][5])


### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

n=int(input())
s=input()
ss=set(s)
for j in range(n):
    for i in ss:
        s=s.replace(i*2,i)

print(len(s))

### FIXED CODE ###

n=int(input())
s=input()
ss=set(s)
l=s[0]
count=1
for j in range(n):
    if l!=s[j]:
        count+=1
        l=s[j]
print(count)
### BUGGY CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)[::-1]
"""
あるn以外の最大公約数が, 最大になる組み合わせ
7 6 8 -> gcd(7,6)=1, gcd(6,8)=2 gcd(7,8)=1
12 15 18 -> gcd(12,15)=3, gcd(15,18)=3, gcd(12, 18)=6
1 2 4 6 -> 2,4,6のやつがでかい
"""
if n == 2:
	print(a[0])
	exit()
ans = 0
for i in range(n):
	tmp = 0
	for j in range(n):
		if j != i:
			tmp = gcd(tmp, a[j])
		if tmp < ans:
			break
	ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
"""
あるn以外の最大公約数が, 最大になる組み合わせ
7 6 8 -> gcd(7,6)=1, gcd(6,8)=2 gcd(7,8)=1
12 15 18 -> gcd(12,15)=3, gcd(15,18)=3, gcd(12, 18)=6
1 2 4 6 -> 2,4,6のやつがでかい
"""
l = [0 for _ in range(n+1)]
tmp = 0
for i in range(n):
	tmp = gcd(tmp, a[i])
	l[i+1] = tmp
r = [0 for _ in range(n+1)]
a = a[::-1]
tmp = 0
for i in range(n):
	tmp = gcd(tmp, a[i])
	r[n-i-1] = tmp

m=[gcd(l[i],r[i+1]) for i in range(n)]
print(max(m))
### BUGGY CODE ###

from functools import reduce
from collections import Counter

N, X = map(int, input().split())
loc = list(map(int, input().split()))
mem = {}

def prime_factors(n):
    if mem.get(n) is not None:
        return mem[n]
    else:
        i = 2
        factors = []
        while i*i <= n:
            if n % i == 0:
                factors.append(i)
                n = n // i
            else:
                i += 1
        if n > 1:
            factors.append(n)
        mem[n] = factors
    return factors


def find_shared_factors(factor1, factor2):
    counters = [Counter(factor1), Counter(factor2)]
    if len(factor1) > 0 and len(factor2) > 0:
        return list(reduce(lambda x, y: x & y, counters).elements())
    elif len(factor2) == 0:
        return factor1
    else:
        return factor2

factors = []
for l in loc:
    factors = find_shared_factors(prime_factors(abs(l-X)), factors)
for i in range(N):
    for j in range(N):
        if i < j:
            factors = find_shared_factors(prime_factors(abs(loc[i]-loc[j])), factors)

r = reduce(lambda x,y: x*y, factors) if len(factors) > 0 else abs(max(loc)-X)

print(r)

### FIXED CODE ###

from functools import reduce
N, X = map(int, input().split())
loc = list(map(int, input().split()))


def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)


print(reduce(gcd, [abs(l-X) for l in loc]))
### BUGGY CODE ###

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])
inf=float("inf")

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int,input().split()))
result = 1
for i in range(n):
  result = result * a_list[i]
  
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
result = 1
if 0 in a_list:
  print(0)
else:
  for a in a_list:
    result = result *a
    if len(str(result)) >= 19:
      if result == 10**18:
        continue
      else:
        result = -1
        break
        
  print(result)
### BUGGY CODE ###

from collections import defaultdict

def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    dp = [defaultdict(int) for i in range(num)]

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2


    dp[0][0] = 2
    dp[0][data[0]] = 1

    dp2 = [defaultdict(int) for i in range(num)]
    dp2[0][0] = 1
    dp2[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp[i-1].keys():
            dp[i][dic_num] += dp[i - 1][dic_num] * 2
            dp[i][dic_num+now_num] += dp[i - 1][dic_num]
            dp2[i][dic_num] += dp2[i - 1][dic_num]
            dp2[i][dic_num + now_num] += dp2[i - 1][dic_num]

    count = 0
    for i in dp[num-1].keys():
        if i >= max_length:
            count += dp[num - 1][i]


    count2 = 0
    for i in dp2[num - 1].keys():
        if i >= max_length:
            count2 += dp2[num - 1][i]

    zennbu = 3 ** num - 3*(2**num - 2) - 3
    hiku = 3 * (count - 2 * count2 + 1)
    ans = zennbu - hiku
    print(ans % 998244353)

    # print('-----')
    # print(sum_data)
    # print(max_length)
    # print(count, count2)
    # print(dp)
    # print(dp2)



if __name__ == '__main__':
    main()
    # print(300**300)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)
### BUGGY CODE ###

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

import sys
import math

if K > 3.5962*math.log(N):
    A = [N]*N
    print(' '.join(map(str, A)))
    sys.exit()
    

lenA = len(A)
for i in range(K):
    B = [0 for _ in range(lenA)]
#    print(B)
    for j in range(lenA):
        num = A[j]
#        print(j, num)
        B[max(0, j - num): min(lenA, j + num + 1)] = [b + 1 for b in B[max(0, j - num): min(lenA, j + num + 1)]]
#        print(j, B)
    if all([a == b for a, b in zip(A,B)]):
#        print('same')
        break
    else:
        A = B
#print(i+1)
print(' '.join(map(str, A)))

### FIXED CODE ###

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

lenA = len(A)
for i in range(K):
    B = [0 for _ in range(lenA)]
#    print(B)
    for j in range(lenA):
        num = A[j]
#        print(j, num)
        if j - num >= 0:
            B[max(0, j - num)] += 1
        else:
            B[0] += 1
        if j + num + 1 < lenA:
            B[min(lenA, j + num + 1)] -= 1
#        print(j, B)
    for i in range(1, lenA):
        B[i] = B[i-1] + B[i]
    if all([a == b for a, b in zip(A,B)]):
#        print('same')
        break
    else:
        A = B
#print(i+1)
print(' '.join(map(str, A)))
### BUGGY CODE ###

def yuk(a, b):
    ans = int(a / b)
    amari = a % b
    if amari != 0:
        ans = yuk(b, amari)
    else:
        ans = b
    return ans

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

ansLst = []
for i in range(len(aLst)):
    ans = 0
    for j in range(len(aLst)):
        if i != j:
            ans = yuk(ans, aLst[j])
    ansLst.append(ans)
ansLst.sort(reverse=True)
print(ansLst[0])

### FIXED CODE ###

import fractions
N = int(input())
aLst = list(map(int, input().split()))

lans = 0
llst = [0] * (N + 1)
rans = 0
rlst = [0] * (N + 1)

for i in range(N):
    lans = fractions.gcd(lans, aLst[i])
    llst[i + 1] = lans

for i in range(N - 1, -1, -1):
    rans = fractions.gcd(rans, aLst[i])
    rlst[i] = rans

ansMax = 0
for i in range(N):
    ansMax = max(ansMax, fractions.gcd(llst[i], rlst[i + 1]))

print(ansMax)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,k=mii()
arr=limii()
aa=[]
for i in range(n):
    arri=arr[i]
    aa.append((arri*(arri+1)//2)/arri)

chk=0
for i in range(n-k+1):
    if chk < sum(aa[i:i+k]):chk=sum(aa[i:i+k])

print(chk)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,k=mii()
arra=limii()
arr=[]
s=[0]
chk=0
for i in range(n):
    arri=arra[i]
    arr.append((arri*(arri+1)//2)/arri)
    

for i in arr:s.append(s[-1]+i)

for i in range(n-k+1):
    chk=max(chk,s[i+k]-s[i])

print(chk)
### BUGGY CODE ###

import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
p=12231472983974394769
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,p-2,p)%p)
  elif a*b<0:
    AA.append(a*pow((-b),p-2,p)%p)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

### FIXED CODE ###

import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
p=137053438808121949
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,p-2,p)%p)
  elif a*b<0:
    AA.append(a*pow((-b),p-2,p)%p)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)
### BUGGY CODE ###

n=int(input())
numeros=[int (x) for x in input().split()]
qtd=[]
K=1
while True:
    cont=0
    cont1=0
    for num in numeros:
        if num<K:
            cont+=1
        else:
            cont1+=1
    if cont==cont1:
        qtd.append(K)
    K+=1
    if K>max(numeros):
        break

print(len(qtd))

### FIXED CODE ###

k = int(input())
seqS=input().split(" ")
num=[]
for q in seqS:
    num.append(int(q))
contador,abc,arc=0,0,0
num.sort() #ORGANIZA
#num do meio
print(num[int(len(num)/2)]- num[int(len(num)/2)-1])