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

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=0
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z+=1
        if z>=k:return True
    return False

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        x_subsub=x_sub2-x_sub1
        for i2 in range(n):
            ans_sub=inf
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min(x_subsub*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min(x_subsub*(y_sub2-y_sub1),ans)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    # S = "1" * 200000
    S = S[::-1]

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        # print("-----")
        # print(f"i: {i}")
        # print(f"tot: {tot}")
        # print(f"S[i]: {S[i]}")
        # print(f"x: {x}")
        # print(f"cnt: {cnt}")
        # print(f"cnt[tot]: {cnt[tot]}")
        # print(f"ans: {ans}")

        cnt[tot] += 1
        tot += int(S[i]) * x
        tot %= 2019
        ans += cnt[tot]
        x = x * 10
    
    # print("-----")
    # print(f"i: {i}")
    # print(f"tot: {tot}")
    # print(f"S[i]: {S[i]}")
    # print(f"x: {x}")
    # print(f"cnt: {cnt}")
    # print(f"cnt[tot]: {cnt[tot]}")
    # print(f"ans: {ans}")
    
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()
    # S = "1" * 200000
    S = S[::-1]

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        # print("-----")
        # print(f"i: {i}")
        # print(f"tot: {tot}")
        # print(f"S[i]: {S[i]}")
        # print(f"x: {x}")
        # print(f"cnt: {cnt}")
        # print(f"cnt[tot]: {cnt[tot]}")
        # print(f"ans: {ans}")

        cnt[tot] += 1
        tot = (tot + (int(S[i]) * x)) % 2019
        ans += cnt[tot]
        x = (x * 10) % 2019
    
    # print("-----")
    # print(f"i: {i}")
    # print(f"tot: {tot}")
    # print(f"S[i]: {S[i]}")
    # print(f"x: {x}")
    # print(f"cnt: {cnt}")
    # print(f"cnt[tot]: {cnt[tot]}")
    # print(f"ans: {ans}")
    
    print(ans)


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

from functools import reduce
from fractions import gcd

def gcd_list(numbers):
    return reduce(gcd, numbers)

def resolve():
    n = int(input())
    ans = 0
    aaa = list(map(int, input().split()))
    for i in range(n):
        l = aaa[:i] + aaa[i+1:]
        g = gcd_list(l)
        ans = max(ans, g)
    print(ans)
resolve()

### FIXED CODE ###

from fractions import gcd


def resolve():
    n = int(input())
    aaa = [0] + list(map(int, input().split())) + [0]
    lll = [0 for i in range(n+2)]
    rrr = [0 for i in range(n+2)]
    for i in range(1, n+1):
        lll[i] = gcd(lll[i-1], aaa[i])
    for i in range(n,0,-1):
        rrr[i] = gcd(rrr[i+1], aaa[i])
    z = [gcd(lll[i-1],rrr[i+1]) for i in range(1,n+1)]
    print(max(z))
resolve()
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
for i in range(1,n-1):
    for j in range((i+1),n):
        for k in range((j+1),n+1):
            if not j-i == k-j:
                if i<j<k:
                    if not s[i-1] == s[j-1]:
                        if not s[i-1] == s[k-1]:
                            if not s[j-1] == s[k-1]:
                                count +=1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
all = s.count("R")*s.count("G")*s.count("B")
for x in range(n-1):
    for y in range(1,(n-1-x)//2+1):
        if s[x] != s[x+y] and s[x]!= s[x+2*y]\
        and s[x+y]!=s[x+2*y]:
            all -=1
print(all)
### BUGGY CODE ###

import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        board[x][y] = p
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    heapq.heappush(q, (i, j, p+1))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()


### FIXED CODE ###

import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()
### BUGGY CODE ###

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

TEMP = []
for i in range(N-K+1):
    TEMP.append(sum(P[i:i+K]))
ANS = max(TEMP)
print((ANS+K)/2)



### FIXED CODE ###

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

# T[i]に1からiまでの合計値が入っている
# M[i]にiの目があるさいころの期待値が入っている
# T = [0]
# M = [0]
# for j in range(1,1001):
#     T.append(j + T[j-1])
#     K.append(T[j]/j)
# 計算すると(n+1)/2


# M = [0]
# for j in range(1,1001):
#     M.append((j+1)/2)
# # print(K)

# PP = []
# for k in P:
#     PP.append(M[k])
# TEMP = []
ANS = 0
for i in range(N-K+1):
    # TEMP.append(sum(P[i:i+K]))
    if i == 0:
        TEMP = sum(P[i:i+K])
    else:
        TEMP = TEMP - P[i-1] + P[i+K-1]
    if TEMP > ANS:
        ANS = TEMP
# ANS = max(TEMP)
print((ANS+K)/2)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
#print(n,a)

minans=abs(2*a[0]-sum(a))
for i in range(1,n):
  ans=abs(2*sum(a[:i])-sum(a))
  if ans < minans:
    minans = ans
    
print(minans)


### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
#print(n,a)
suma=sum(a)
minans=abs(2*a[0]-suma)
#print(minans)

mydata=0
for i in range(0,n-1):
  mydata+=a[i]
  ans=abs(2*mydata-suma)
  if ans < minans:
    minans = ans
    
print(minans)
### BUGGY CODE ###

def split(word):
    return [char for char in word]
N=int(input())
S=input()
Slist=split(S)
Rcounter=0
Bcounter=0
Gcounter=0
for i in range(0,N):
    if Slist[i]=='R':
        Rcounter=Rcounter+1
    if Slist[i]=='B':
        Bcounter=Bcounter+1
    if Slist[i]=='G':
        Gcounter=Gcounter+1
ans=Rcounter*Gcounter*Bcounter
for i in range(0,N):
    for j in range(i+1,N):
        if 2*j-i>N-1:
            break
        flag=0
        if Slist[i]==Slist[j]:
            flag=1
        if Slist[i]==Slist[2*j-i]:
            flag=1
        if Slist[j]==Slist[2*j-i]:
            flag=1
        if flag==0:
            ans=ans-1
print(ans)

### FIXED CODE ###

def split(word):
    return [char for char in word]
N=int(input())
S=input()
Slist=split(S)
Rcounter=0
Bcounter=0
Gcounter=0
for i in range(0,N):
    if Slist[i]=='R':
        Rcounter=Rcounter+1
    if Slist[i]=='B':
        Bcounter=Bcounter+1
    if Slist[i]=='G':
        Gcounter=Gcounter+1
ans=Rcounter*Gcounter*Bcounter
for i in range(0,N):
    for j in range(i+1,N):
        if 2*j-i>N-1:
            break
        if (Slist[i]==Slist[j]) or (Slist[i]==Slist[2*j-i]) or (Slist[j]==Slist[2*j-i]):
            continue
        ans=ans-1
print(ans)
### BUGGY CODE ###


N = int(input())

str_list = [input() for i in range(N)]

cnt_dict = {}

for str in str_list:
    s_str = "".join(sorted(str))
    if s_str not in cnt_dict.keys():
        cnt_dict[s_str] = 1
        continue
    cnt_dict[s_str] += 1

import itertools

total = 0
for key in cnt_dict.keys():
    cnt = cnt_dict[key]
    if cnt < 2:
        continue
    total += len(list(itertools.combinations(range(cnt), 2)))

print(total)

### FIXED CODE ###


N = int(input())

cnt_dict = {}

for i in range(N):
    s_list = list(input())
    s_list.sort()
    s_str = "".join(s_list)
    if s_str not in cnt_dict.keys():
        cnt_dict[s_str] = 1
        continue
    cnt_dict[s_str] += 1

import itertools
comb = itertools.combinations

total = 0
for key in cnt_dict.keys():
    cnt = cnt_dict[key]
    if cnt < 2:
        continue
    total += cnt * (cnt - 1) // 2

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

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

prev = 0
ind = 0
for i in range(n-k+1):
    nex = 0
    for j in range(i,i+k):
        nex += p[j]

    if prev < nex:
        prev = nex
        ind = i

total = 0
for i in range(ind,ind+k):
    total += (sum(tuple(range(1, p[i]+1))))/p[i]

print(total)

### FIXED CODE ###

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

prev = sum(p[1:k])
current = sum(p[1:k])
ind = 0

for i in range(1, n - k + 1):
    current = current - p[i - 1] + p[i + k - 1]

    if prev < current:
        prev = current
        ind = i

total = 0
for i in range(ind, ind + k):
    total += p[i] / 2 + 0.5

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

n=int(input())
li=list(map(int,input().split()))
li.sort()
if li[0]==0:
  print(0)
else:
  ans=1
  for i in li:
    ans*=i
    if ans>1000000000000000000:
        ans=-1
        exit
    else:
        continue
    
  if ans>1000000000000000000:
      print(-1)
  else:
      print(ans)

### FIXED CODE ###

import sys
n=int(input())
li=list(map(int,input().split()))
li.sort()
if li[0]==0:
  print(0)
  sys.exit()
else:
  ans=1
  for i in li:
    ans*=i
    if ans>1000000000000000000:
        print(-1)
        sys.exit()
    else:
        continue
    
  if ans>1000000000000000000:
      print(-1)
  else:
      print(ans)
### BUGGY CODE ###

from math import ceil
import bisect
N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])
cnt = 0

for i in range(N):
    left_pos, hp = L[i]
    if hp <= 0:
        continue
    cnt += hp
    right_ind = bisect.bisect_right([v[0] for v in L], left_pos+2*D)
    for v in range(i, right_ind):
        L[v][1] = max(0, L[v][1] - hp)
print(cnt)


### FIXED CODE ###

from math import ceil
import bisect


N, D, A = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(N)]
L = [[pos, ceil(hp/A)] for pos, hp in L]
L = sorted(L, key=lambda pos: pos[0])

POS = [v[0] for v in L]
ES = [0]*(N+1)
ans, c = 0, 0
for i in range(N):
    c -= ES[i]
    if L[i][1] > c:
        t = L[i][1]-c
        ans += t
        c += t
        ES[bisect.bisect_right(POS, POS[i]+2*D)] += t
print(ans)
### BUGGY CODE ###

s = input()
kids = [0] * len(s)
for i, c in enumerate(s):
    now = i
    if c == "R":
        while s[now + 1] == "R":
            now += 1
        diff = abs(now - i)
        if diff % 2:
            kids[now + 1] += 1
        else:
            kids[now] += 1
    else:
        while s[now - 1] == "L":
            now -= 1
        diff = abs(now - i)
        if diff % 2:
            kids[now - 1] += 1
        else:
            kids[now] += 1
print(" ".join([str(k) for k in kids]))


### FIXED CODE ###

s = list(input())
kids = [0] * len(s)

for d in ["R", "L"]:
    c = 0
    for i in range(len(s)):
        if s[i] == d:
            c += 1
        else:
            kids[i] += c // 2
            kids[i - 1] += (c + 1) // 2
            c = 0
    s.reverse()
    kids.reverse()

print(" ".join([str(k) for k in kids]))
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    import functools
    import operator

    n = int(input().rstrip())


    result = functools.reduce(operator.mul, list(range(1, n + 1)))
    print(result % 1000000007)



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()
# row = [int(input().rstrip()) for _ in range(n)]

def resolve():
    import sys
    input = sys.stdin.readline
    import functools
    import operator

    n = int(input().rstrip())

    ans = 1
    for i in range(1, n+1):
        ans *= i
        ans = ans % 1000000007

    print(ans)



if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = 2*[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+2*[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = [[CH+1,CW+1]]
Q = deque([[CH+1,CW+1]])
ans = 0

while P:
  P = []
  while Q:
    y,x = Q.popleft()
    P+=[[y,x]]
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q+=[[y+dy,x+dx]]

  if S[DH+1][DW+1]!=".":
    print(S[DH+1][DW+1])
    exit()
  else:
    ans+=1
    for y,x in P:
      for dy,dx in [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans
          Q+=[[y+dy,x+dx]]

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

### FIXED CODE ###

from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
A = [0]*(len(S)+1)
for i in range(len(S)+1):
    L = S[:i]
    R = S[i:]
    # print('L=', L)
    # print('R=', R)
    l = 0
    r = 0
    if L != '':
        T = len(L)
        for k in range(T):
            if L[T-k-1] != '<':
                l = k
                break
        else:
            l = T
    if R != '':
        U = len(R)
        for j in range(U):
            if R[j] != '>':
                r = j
                break
        else:
            r = len(R)
    A[i] = max(l, r)
# print(A)
print(sum(A))


### FIXED CODE ###

S=input()
N=len(S)+1
L=[0]*N
R=[0]*N
ans=[0]*N
for i in range(1,N):
    if S[i-1]=='<':
        L[i]=L[i-1]+1
    if S[N-i-1]=='>':
        R[N-i-1]=R[N-i]+1
for i in range(N):
    ans[i]=max(L[i], R[i])
print(sum(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    ans = 0
    if S == '0':
        print(ans)
        return
    N = len(S)
    for i in range(min(S.count('0'), S.count('1'))):
        if len(S) > 0:
            S = S.replace('10', '')
            S = S.replace('01', '')
        else:
            break
    ans = N - len(S)
    print(ans)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    stack = []
    N = len(S)
    for i, s in enumerate(S):
        if i == 0:
            stack.append(s)
        else:
            if len(stack) == 0:
                stack.append(s)
            else:
                if s != stack[-1]:
                    tmp = stack.pop()
                else:
                    stack.append(s)
    print(N - len(stack))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = str(input())
    solve(S)

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

import sys
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()
from_one = []
to_n = []

for _ in range(m):
    a, b = na()
    if a == 1:
        from_one.append(b)
    if b == n:
        to_n.append(a)

p = False
for i in from_one:
    if i in to_n:
        print("POSSIBLE")
        p = True
if not p:
    print("IMPOSSIBLE")
        


### FIXED CODE ###

import sys
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()
from_one = [0] * n
to_n = [0] * n

for _ in range(m):
    a, b = na()
    if a == 1:
        from_one[b] = 1
    if b == n:
        to_n[a] = 1

p = False
for i, j in zip(from_one, to_n):
    if i == 1 and j ==1:
        print("POSSIBLE")
        p = True
        break
if not p:
    print("IMPOSSIBLE")
### BUGGY CODE ###

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

d = 0
for i in range(n-k+1):
  if d < sum(p[i:k+i]):
    d = sum(p[i:k+i])
    d_start = i

ans = 0
for i in range(k):
  ans += (p[d_start + i] + 1)/2
  
print(ans)

### FIXED CODE ###

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

d_tmp = sum(p[0:k])
d_max = sum(p[0:k])
for i in range(n-k):
  d_tmp = d_tmp + p[k+i] - p[i]
  d_max = max(d_max,d_tmp)

ans = (d_max + k)/2
print(ans)
### BUGGY CODE ###

import sys
n, k = map(int, input().split())
A = list(map(int, input().split()))
 
for r in range(k):
    B = [0 for i in range(n+1)]
    for i in range(n):    
        d_min = max(0, i - A[i])
        d_max = min(n, i + A[i] + 1)
        B[d_min] += 1
        B[d_max] -= 1
        # print(d_min, d_max, B)
    t = 0
    flag = True
    for i in range(n):
        t += B[i]
        if A[i] != t:
            flag = False
        A[i] = t
    if flag:
        break
    # print(A, B)

print(' '.join(map(str, A)))

### FIXED CODE ###

# 東京海上日動 プログラミングコンテスト2020 C
import numpy as np
from numba import njit
n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def imos(n, A):
    B = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        left = max(0, i - A[i])
        right = min(n, i + A[i] + 1)
        B[left] += 1
        B[right] -= 1
    B = np.cumsum(B)
    return B[:-1]

def solve(n,k,A):
    for i in range(k):
        A = imos(n, A)
        min_A = min(A)
        if min_A == n:
            return A
    return A

ANS = solve(n, k, A)
print(' '.join(map(str, ANS)))
### BUGGY CODE ###

K, Q = map(int, input().split())
*D, = map(int, input().split())
for q in range(Q):
    n, x, m = map(int, input().split())
    D1 = [d % m for d in D]
    r = (n - 1) % K
    cnt_0 = D1.count(0) * ((n - 1) // K) + D1[:r].count(0)
    a = x
    # 第n-1項を求める
    b = a + sum(D1) * ((n - 1) // K) + sum(D1[:r])
    # 繰り上がりの回数
    cnt_p = b // m - a // m
    cnt_n = (n - 1) - cnt_0 - cnt_p
    print(cnt_n)


### FIXED CODE ###

K, Q = map(int, input().split())
*D, = map(int, input().split())
for q in range(Q):
    n, x, m = map(int, input().split())
    r = (n - 1) % K
    D1r_count0 = 0
    D1_count0 = 0
    D1_sum = 0
    D1r_sum = 0
    for k in range(K):
        if k < r:
            if D[k] % m == 0:
                D1r_count0 += 1
            D1r_sum += D[k] % m
        if D[k] % m == 0:
            D1_count0 += 1
        D1_sum += D[k] % m
    cnt_0 = D1_count0 * ((n - 1) // K) + D1r_count0
    a = x
    # 第n-1項を求める
    b = a + D1_sum * ((n - 1) // K) + D1r_sum
    # 繰り上がりの回数
    cnt_p = b // m - a // m
    cnt_n = (n - 1) - cnt_0 - cnt_p
    print(cnt_n)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 10000000000
total = sum(a)
for i in range(1, N):
    sunuke = a[:i]
    Sum = sum(sunuke)
    if abs(Sum - (total - Sum)) <= ans:
        ans = abs(Sum - (total - Sum))
print(ans)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 10000000000
total = sum(a)
sunuke = 0
for i in range(N-1):
    sunuke += a[i]
    dif = abs(2 * sunuke - total)
    if dif <= ans:
        ans = dif
print(ans)