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

from collections import defaultdict

def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    m = defaultdict(int)
    for x, y, c in xyc:
        y += c * K
        x1, y1 = x % K2, y % K2
        x2, y2 = x1 + K, y1 + K
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x2, y1] -= 1
        m[x1, y2] -= 1
        x1, y1 = (x + K) % K2, (y + K) % K2
        x2, y2 = x1 + K, y1 + K
        m[x1, y1] += 1
        m[x2, y2] += 1
        m[x2, y1] -= 1
        m[x1, y2] -= 1

    ms = [[0] * (K2 + 1) for i in range(K2 + 1)]
    for y in range(0, K2):
        ms0 = ms[y]
        ms1 = ms[y - 1]
        for x in range(0, K2):
            ms0[x] = m[x, y] + ms0[x-1] + ms1[x] - ms1[x-1]
    
    rmax = 0
    for y in range(K, K2):
        for x in range(K, K2):
            rcount = ms[y][x]
            rmax = max(rmax, rcount, N - rcount)

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))


### FIXED CODE ###

def calc(K, xyc):
    K2 = K * 2
    N = len(xyc)

    p = [[0] * K2 for i in range(K2)]
    for x, y, c in xyc:
        y += c * K
        p[x % K2][y % K2] += 1
        p[(x + K) % K2][(y + K) % K2] += 1

    def isum(xs):
        r = 0
        yield r
        for x in xs:
            r += x
            yield r

    psum = [list(isum(row)) for row in p]
    pksum = [[b - a for a, b in zip(row, row[K:])] for row in psum]

    rmax = N / 2
    for y in range(K):
        rcount = sum(row[y] for row in pksum[:K])
        for x in range(K):
            rmax = max(rmax, rcount, N - rcount)
            rcount += -pksum[x][y] + pksum[x + K][y]

    return rmax

if __name__ == '__main__':
    N, K = [int(e) for e in input().split()]
    xyc = [(int(x), int(y), c == "W") for x, y, c in [input().split() for i in range(N)]]
    print(calc(K, xyc))
### BUGGY CODE ###

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
sys.setrecursionlimit(10**6)
N=int(input())
A=[0]+list(map(int,input().split()))

E=[[] for i in range(N+1)]
for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

USE=[0]*(N+1)
USE[1]=1
ANS=[0]*(N+1)

import bisect
def dfs(x,DP):
    #print(x,DP)
    pos=bisect.bisect_left(DP,A[x])
    #print(pos)
    if pos<len(DP):
        DP=list(DP)
        DP[pos]=A[x]
        DP=tuple(DP)
    else:
        DP+=(A[x],)
    #print(DP)

    ANS[x]=len(DP)

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            dfs(to,DP)

dfs(1,tuple())

print(*ANS[1:])
    


### FIXED CODE ###

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

N=int(input())
A=[0]+list(map(int,input().split()))

E=[[] for i in range(N+1)]
for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

USE=[0]*(N+1)
USE[1]=1
ANS=[0]*(N+1)
DP=[]

def dfs(x):
    pos=bisect.bisect_left(DP,A[x])
    
    if pos<len(DP):
        changepos=pos
        old=DP[pos]
        
        DP[pos]=A[x]
    else:
        changepos=pos
        old=-1
        
        DP.append(A[x])

    ANS[x]=len(DP)

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            dfs(to)

    if old==-1:
        DP.pop()
    else:
        DP[changepos]=old

dfs(1)

print(*ANS[1:])
### BUGGY CODE ###

import sys
 
 
def resolve():
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1],
                                   dp[i + 1][j],
                                   dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = ''
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])
 
 
resolve()


### FIXED CODE ###

def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
 
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()
### BUGGY CODE ###

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

cnt=0
for i in range(n):
    for j in range(i):
        if p[j]<p[i]:
            cnt+=1
            break
print(n-cnt)

### FIXED CODE ###

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

a=p[0]
cnt=1
for i in range(1,n):
    if a>=p[i]:
        cnt+=1
        a=p[i]

print(cnt)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    K = NI()
    ans = 0
    m = 0
    while True:
        m = (m * 10 + 7) % K
        ans += 1
        if m == 0: break
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    K = NI()
    ans = 0
    m = 0
    while True:
        m = (m * 10 + 7) % K
        ans += 1
        if m == 0 or ans > K: break
    if ans <= K:
        print(ans)
    else:
        print(-1)


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

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[0, 0]
    cl = collections.defaultdict(int)
    cl[0, 0] = 1
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            for xv, yv in [[x + 1, y], [x, y + 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and a[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv] = cost + 1
                        cl[xv, yv] = cl[x, y]
                    else:
                        cl[xv, yv] += cl[x, y]
                        cl[xv, yv] % mod
        else:
            break
    print(cl[h-1, w-1] % mod)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    dp = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            elif i == 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[-1][-1])


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

import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

#nCr
def comb(n,r):
    x = 1
    y = 1
    for i in range(r):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

ncr = [0]*(n+1)
for i in range(1,n+1):
    ncr[i] = comb(n-i,k-1)

ans = 0
for i in range(n):
    ans += (A[n-1-i] * ncr[i+1] - A[i] * ncr[i+1])

print(ans % mod)


### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = sorted(inpl())

f=[1]
for i in range(1,n+1):
  f.append(f[-1]*i % mod)

#nCr
def comb(n,r):
    if n <= 0 or r <= 0:
        return 0
    x = f[n] % mod
    y = f[r] * f[n-r] % mod
    return (x * pow(y, mod-2, mod) % mod)

ans = 0
for i in range(n):
    c = comb(n-i-1,k-1)
    ans += A[n-1-i] * c - A[i] * c
    ans %= mod
    if c == 1:
        break

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

n, k = map(int, input().split())
s = set()
# lr = []
for _ in range(k):
    l, r = map(int, input().split())
    # lr.append(tuple(map(int, input().split())))
    for tmp in range(l, r+1):
        s.add(tmp)
mod = 998244353

dp = [0]*n
dp[0] = 1

for i in range(1, n):
    # for l, r in lr:
    for ss in s:
        if i-ss >= 0:
            dp[i] += dp[i-ss]
    dp[i] %= mod

print(dp[-1]%mod)

### FIXED CODE ###

n, k = map(int, input().split())
lr = []
for _ in range(k):
    lr.append(tuple(map(int, input().split())))
mod = 998244353

dp = [0]*n
dp[0] = 1

acc = [0]*n
acc[0] = 1

for i in range(1, n):
    for l, r in lr:
        if 0 <= i-r and i-l < i:
            dp[i] += acc[i-l]-acc[i-r-1]
        elif i-r < 0 and i-l < i:
            dp[i] += acc[i-l]
        elif i-r < 0 and i <= i-l:
            dp[i] += acc[i-1]
        elif 0 < i-r and i <= i-l:
            dp[i] += acc[i-1]-acc[i-r-1]
    acc[i] = acc[i-1]+dp[i]%mod

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = INT()

def make_divisors(n):
	for i in range(floor(n**0.5), 0, -1):
		if n % i == 0:
			if i <= 10**9 and S//i <= 10**9:
				return i

			if i != n // i:
				if n//i <= 10**9 and S//(n//i) <= 10**9:
					return i

x = make_divisors(S)
y = S//x
print(0, 0, 0, y, x, 0)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = INT()

def make_divisors(n):
	for i in range(floor(n**0.5), 0, -1):
		if n % i == 0:
			if i <= 10**9 and n//i <= 10**9:
				return i

			if i != n // i:
				if n//i <= 10**9 and S//(n//i) <= 10**9:
					return i

a = ceil(S**(1/2))
b = ceil(S**(1/2))
if a * b == S:
	c = d = 0
else:
	c = make_divisors(a*b-S)
	if c == 0:
		c = d = 0
	else:
		d = ((a*b)-S)//c
print(0, 0, a, d, c, b)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra

n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)

M = [[float("inf")] * 2**n for i in range(2**n)]

for i in range(2**n):
    M[i][i] = 0

for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    for j in range(2**n):
        for k in range(2**n):
            if (t-(k-j)) ^ (k-j) == t:
                # print(t,j)
                M[j][k] = min(M[j][k], A[i][0])
# print(M)

d = dijkstra(M, indices = 0)

ans = d[-1]
if ans == float("inf"):
    ans = -1
print(int(ans))


### FIXED CODE ###

n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)
T = []
for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    T.append(t)


n2 = 2**n

DP = [[float("inf") for i in range(n2)] for j in range(m+1)]
for i in range(m+1):
    DP[i][0] = 0

for i in range(1,m+1):
    t = T[i-1]
    for j in range(n2):
        # print(i,j,t)
        # print(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j|t] = min(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j] = min(DP[i][j], DP[i-1][j])
        # print(DP[i][j|t])

ans = DP[-1][-1]
if ans == float("inf"):
    ans = -1
print(int(ans))
### BUGGY CODE ###

from functools import lru_cache

n = int(input())
s = input()
point = 0

# 100の位
for i in range(10):
    # Sのn-2番目までにiがあるか
    now_i = -1
    for a in range(n-2):
        if s[a] == str(i):
            now_i = a
            break
    # 作れない場合以降の探索は打ち切り
    if now_i == -1:
        continue
    # 10の位
    for j in range(10):
        now_j = -1
        for b in range(now_i+1,n-1):
            if s[b] == str(j):
                now_j = b
                break
        if now_j == -1:
            continue
        # 1の位
        for k in range(10):
            for c in range(now_j+1,n):
                # 暗証番号がそろった
                if s[c] == str(k):
                    point += 1
                    break

print(point)

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

print(count(1000))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import bisect
from collections import defaultdict
h, w, d = map(int, input().split())
p = dict()
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (x, i, j)
        D[x%d].append((x, i, j))

for key in D.keys():
    D[key].sort()

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    v = D[a%d]
    l = v.index(p[a])
    r = l + (b-a)//d
    tmp = v[l:r+1]
    _, s, t = tmp[0]
    ans = 0
    for _, u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [0]*(h*w+1)
for i in range(h*w+1):
    if d < i:
        dp[i] = dp[i-d] + abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[b]-dp[a]
    print(ans)
### BUGGY CODE ###

import copy

S=input()

N=len(S)
M=[]
for s in S:
    if s == 'R':
        M.append(1)
    else:
        M.append(-1)


def move(C):
    D=[0] * N
    for i,c in enumerate(C):
        D[i+M[i]] += c
    return D



c=[1] * N
d=[0] * N
even_c = [0] * N

i=0
while True:
    d = move(c)
    if c == even_c:
        break
    if i % 2 == 0:
        even_c = c
    c = d
    i+=1

for c in even_c:
    print(str(c)+' ',end='')
print()

### FIXED CODE ###

S=input()

N=len(S)
RLs=[]
Rs=[]
Ls=[]

rlen=0
llen=0
for i in range(N):

    if S[i]=='R':
        rlen+=1
        if S[i:i+2] == 'RL':
            RLs.append(i)
            Rs.append(rlen)
            rlen=0
    elif S[i]=='L':
        llen+=1
        if i==N-1 or S[i:i+2] == 'LR':
            Ls.append(llen)
            llen=0

ans = [0]*N
for i,rlpos in enumerate(RLs):
    rr=-(-Rs[i]//2)
    rl=Rs[i]//2

    lr=Ls[i]//2
    ll=-(-Ls[i]//2)

    ans[rlpos]+=rr+lr
    ans[rlpos+1]+=rl+ll

for a in ans:
    print(str(a)+' ',end='')
print()
### BUGGY CODE ###

N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

res = []

for k in range(1, N + 1):
  A_tmp = list(A) # list() to make a new copy and avoid editing the original list
  del A_tmp[k - 1]
  A_tmp = Counter(A_tmp)

  n = 0
  for i in range(len(A_tmp)):
    j = list(A_tmp.values())[i]
    if j >= 2:
      n += math.factorial(j) // math.factorial(2) // math.factorial(j - 2)
  res.append(n)



print('\n'.join([str(s) for s in res]))

### FIXED CODE ###

N = int(input())
A = [int(k) for k in input().split(' ')]

from collections import Counter 
import math 

res = [] # solution for each key in A
res_list = {} # solution for each value in A

# counter ver
A_c = Counter(A)
l = len(A_c)

def ncr(j):
  return int(j * (j-1) / 2) if j >= 2 else 0

# store ncr for each value 
combs = {k: ncr(v) for k, v in A_c.items()}

s = sum(combs.values())
  
for m in A_c.keys():
  res_list[m] = s - combs[m] + ncr(A_c[m] - 1)

for k in range(N):
  res.append(res_list[A[k]])
print('\n'.join([str(s) for s in res]))
### BUGGY CODE ###

import math
import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix


def num():
    return int(input())


def nums():
    return map(int,input().split())

n,m = nums()

root = [list(nums()) for _ in range(m)]

res = [[math.inf]*n  for _ in range(n)]

for i in range(n):
    res[i][i] = 0

for i,j in root:
     
    res[i-1][j-1] = res[j-1][i-1] = 1

res = csr_matrix(res)
res,t = shortest_path(res, indices=0, return_predecessors=True)

if -9999 in res[1:]:
    print('No')
else:
    print('Yes')
    [print(i+1) for i in t[1:]]

### FIXED CODE ###

from collections import deque
import sys


readline = sys.stdin.readline
readall = sys.stdin.read
ins = lambda: readline().rstrip()
ini = lambda: int(readline().rstrip())
inm = lambda: map(int, readline().split())
inl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')


n,m = inm()
W = [[] for _ in range(n)]
for _ in range(m):
    a,b = inm()
    W[a-1].append(b-1)
    W[b-1].append(a-1)

res = [0] * n
dis = [n] * n
dis[0] = 0

q = deque()
q.append(0)
while q:
    c = q.popleft()
    for i in W[c]:
        if dis[i] > dis[c] + 1:
            dis[i] = dis[c] + 1
            res[i] = c + 1
            q.append(i)

print('Yes')
prl(res[1:])
### BUGGY CODE ###

import numpy as np


def main():
    n, k = map(int, input().split())
    ps = (np.array(list(map(int, input().split()))) + 1) / 2

    ans = -float("inf")
    ans = max([sum(ps[i:i+k]) for i in range(n-k+1)])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    ps = list(map(int, input().split()))
    e = [(1+p)/2 for p in ps]

    s = [0]
    for i in range(n):
        s.append(s[i]+e[i])

    ans = max([s[i+k] - s[i] for i in range(n-k+1)])
    print(ans)


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

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        l = abs(L[i] - L[j])
        r = L[i] + L[j]

        if l < L[i]:
            li = bisect.bisect(L, l, hi=i)
        else:
            li = bisect.bisect(L, l, lo=i, hi=j)

        ri = bisect.bisect_left(L, r, lo=j)
        for k in range(li, ri):
            if k == i or k == j: continue
            if k < i:
                ans.add((L[k], L[i], L[j]))
            elif k < j:
                ans.add((L[i], L[k], L[j]))
            else:
                ans.add((L[i], L[j], L[k]))

print(len(ans))


### FIXED CODE ###

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j)
        ans += ri - j - 1

print(ans)