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

# coding: utf-8
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

dp = [[0 for _ in range(S+1)] for i in range(N+1)]

for k in range(0, N):
  for s in range(1, S+1):
    dp[k+1][s] += (2 * dp[k][s] - dp[k-1][s]) % mod
  if S > A[k+1]:
    for s in range(1,S-A[k+1]+1):
      dp[k+1][s+A[k+1]] += (dp[k][s] - dp[k-1][s]) % mod
  if A[k+1] <= S:
    dp[k+1][A[k+1]] += k+1

print(dp[N][S] % mod)

### FIXED CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt[n,:] %= 998244353
print(dt[N,S] % 998244353)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split())) + [0]*K

dp = [float('inf') for _ in range(N+K)]
dp[0] = 0
'配るdp'
for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split())) + [0]*K

dp = [float('inf') for _ in range(N+K)]
dp[0] = 0
'配るdp'
for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]))

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

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    H, W = map(int, readline().split())
    A = np.array([
        list(map(lambda x: int(x) % 2,
                 readline().split())) for _ in range(H)
    ])
    B = np.reshape(np.arange(H * W), [H, W])
    for i in range(1, H, 2):
        A[i, :] = A[i, :][::-1]
        B[i, :] = B[i, :][::-1]

    C = A.ravel()
    D = B.ravel()

    aa = []
    for i in range(len(C) - 1):
        if C[i] % 2 != 0:
            C[i + 1] += 1
            aa.append(i)

    print(len(aa))
    for i in aa:
        w0, h0 = divmod(D[i], W)
        w1, h1 = divmod(D[i + 1], W)
        print(w0 + 1, h0 + 1, w1 + 1, h1 + 1)


main()


### FIXED CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    H, W = map(int, readline().split())
    A = np.array([
        list(map(lambda x: int(x) % 2,
                 readline().split())) for _ in range(H)
    ])

    aa = []
    for h in range(H):
        for w in range(W - 1):
            if A[h, w] == 1:
                A[h, w + 1] += 1
                aa.append([h + 1, w + 1, h + 1, w + 2])

    for h in range(H - 1):
        w = W - 1
        if A[h, w] % 2 != 0:
            A[h + 1, w] += 1
            aa.append([h + 1, w + 1, h + 2, w + 1])

    print(len(aa))

    for a in aa:
        print(*a)


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, K = inpl()
A = sorted(inpl(), reverse=True)

DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))  

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False] * K
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP1[j+a] = True
    DP = DP1 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))
### BUGGY CODE ###

# C - Five Transportations 

N = int(input())
A,B,C,D,E = (int(input()),int(input()),int(input()),int(input()),int(input()))
        
turn = 0
x1,x2,x3,x4,x5 = 0,0,0,0,0
y1,y2,y3,y4,y5 = 0,0,0,0,0
x0 = N
y0 = N

while x0+x1+x2+x3+x4 != 0:
    turn += 1
    
    # Aの判定
    if x0 > A:
        y1 += A
        y0 -= A
    elif 0 < x0 <= A:
        y1 += x0
        y0 -= x0
    else:
        pass
    
    # Bの判定
    if x1 > B:
        y2 += B
        y1 -= B
    elif 0 < x1 <= B:
        y2 += x1
        y1 -= x1
    else:
        pass
    
    # Cの判定
    if x2 > C:
        y3 += C
        y2 -= C
    elif 0 < x2 <= C:
        y3 += x2
        y2 -= x2
    else:
        pass
     
    # Dの判定
    if x3 > D:
        y4 += D
        y3 -= D
    elif 0 < x3 <= D:
        y4 += x3
        y3 -= x3
    else:
        pass
        
    # Eの判定
    if x4 > E:
        y5 += E
        y4 -= E
    elif 0 < x4 <= E:
        y5 += x4
        y4 -= x4
    else:
        pass
    
    # x => y
    x0,x1,x2,x3,x4,x5 = y0,y1,y2,y3,y4,y5
    

print(turn)
    
             

### FIXED CODE ###

import math

N = int(input())
a = [int(input()) for _ in range(5)]

print(math.ceil(N / min(a)) + 4)
### BUGGY CODE ###

def digitSum(n):
    s = str(bin(n))
    s = s[2:]
    array = list(map(int, s))
    return sum(array)
N = int(input())
A = []
X = []
Y = []
res = 0
for i in range(N):
    a = int(input())
    A.append(a)
    X_temp = []
    Y_temp = []
    for j in range(a):
        x,y = map(int,input().split())
        X_temp.append(x)
        Y_temp.append(y)
    X.append(X_temp)
    Y.append(Y_temp)
for bit in range(1 << N):
    for i in range(1 << N):
        judge = True
        for j in range(N):
            if (i >> j) & 1:#もしAjが正直者だったら
                for k in range(A[j]):
                    if (i >> X[j][k]-1) & 1 != Y[j][k]:
                        judge = False
            else:
                for k in range(A[j]):
                    if (i >> X[j][k]-1) & 1 == Y[j][k]:
                        judge = False
        if judge:
            res = max(res,digitSum(i))
print(res)

### FIXED CODE ###

def digitSum(n):
    s = str(bin(n))
    s = s[2:]
    array = list(map(int, s))
    return sum(array)
N = int(input())
A = []
X = []
Y = []
res = 0
for i in range(N):
    a = int(input())
    A.append(a)
    X_temp = []
    Y_temp = []
    for j in range(a):
        x,y = map(int,input().split())
        X_temp.append(x)
        Y_temp.append(y)
    X.append(X_temp)
    Y.append(Y_temp)
for i in range(1 << N):
    judge = True
    for j in range(N):
        if (i >> j) & 1:#もしAjが正直者だったら
            for k in range(A[j]):
                if (i >> X[j][k]-1) & 1 != Y[j][k]:
                    judge = False
        """else:#もしAjが不親切ものだったら。不親切者も正しいことをいうこともある。
            for k in range(A[j]):#
                if (i >> X[j][k]-1) & 1 == Y[j][k]:
                    judge = False"""
    if judge:
        res = max(res,digitSum(i))
print(res)
### BUGGY CODE ###

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

prev = 1
for i in range(k):
    prev *= a[i]
old = 0

for i in range(k, n):
    score = prev*a[i] / a[old]
    if score <= prev:
        print('No')
        #exit()
    else:
        print('Yes')
    prev = score
    old += 1

### FIXED CODE ###

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

for i in range(n-k):
    if a[i+k] <= a[i]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
import collections
import numpy as np
def count_ident(v):
    c = collections.Counter(v)
    val_list=np.array(list(c.values()))
    v_count=val_list*(val_list-1)/2
    print(int(sum(v_count)))

import copy
c = copy.deepcopy(a)    
for i in range(len(a)):
    tmp = copy.deepcopy(a)    
    tmp.pop(i)
    count_ident(tmp)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
import collections
c = collections.Counter(a)
val_list=list(c.values())
v_count=map(lambda x: x * (x-1), val_list)
total_count=int(sum(v_count)/2)

for i in a:
    print(total_count-(c[i]-1))
### BUGGY CODE ###

from collections import Counter
from itertools import combinations

def solve(N, As):
    data = {}
    for i, a in enumerate(As):
        data.setdefault(a, []).append(i)
    d_pairs = []
    counters = Counter()
    keys = list(sorted(data.keys()))
    for v in combinations(keys, 2):
        if bin(v[0] + v[1]).count("1") == 1:
            d_pairs.append((v[0], v[1]))
            counters.update([v[0]] * len(data[v[0]]))
            counters.update([v[1]] * len(data[v[1]]))
    for v in keys:
        if bin(v * 2).count("1") == 1:
            d_pairs.append((v, v))
            counters.update([v] * len(data[v]))
    cost = []
    for p in d_pairs:
        if p[0] != p[1]:
            c1 = counters[p[0]] if bin(p[0]).count("1") != 1 else 10 ** 10
            c2 = counters[p[1]] if bin(p[1]).count("1") != 1 else 10 ** 10
            cost.append((c1 + c2, p[0], p[1]))
        else:
            cost.append((10 ** 10 * 2 + 1, p[0], p[1]))
    ans = 0
    cost.sort()
    for cost_pair in sorted(cost):
        if cost_pair[1] != cost_pair[2]:
            while len(data[cost_pair[1]]) > 0 and len(data[cost_pair[2]]) > 0:
                ans += 1
                data[cost_pair[1]].pop()
                data[cost_pair[2]].pop()
        else:
            while len(data[cost_pair[1]]) > 1:
                ans += 1
                data[cost_pair[1]].pop()
                data[cost_pair[2]].pop()
    return ans

if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(solve(N, As))


### FIXED CODE ###

from collections import Counter

def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    for d in reversed(sorted(As)):
        n = (2 ** d.bit_length()) - d
        if d != n:
            if C[d] > 0 and C.get(n, 0) > 0:
                C[d] -= 1
                C[n] -= 1
                ans += 1
        else:
            ans += C[d]//2
            C[d] = 0
    return ans
 
 
if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(ans_solve(N, As))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
for i in range(n):
    tmp = a.pop(0)
    print(max(a))
    a.append(tmp)
    

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_max = max(a)
ind_M = a.index(a_max)
tmpl = a
tmpl.pop(ind_M)
for i in range(n):
    if i != ind_M:
        print(a_max)
    else:
        print(max(tmpl))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a = sorted(a,reverse=True)
b = sorted(b,reverse=True)
c = sorted(c,reverse=True)

l = []
for i in range(min(500,x)):
    for j in range(min(500,y)):
        for t in range(min(500,z)):
            l.append(a[i] + b[j] + c[t])
l = sorted(l,reverse=True)
for i in range(k):
    print(l[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

l = []
for i in range(x):
    for j in range(y):
            l.append(a[i] + b[j])

l = sorted(l,reverse=True)
ll = []
for i in range(min(len(l),k)):
    for j in range(z):
        ll.append(l[i] + c[j])

ll = sorted(ll,reverse=True)
for i in range(k):
    print(ll[i])
### BUGGY CODE ###


N = int(input())

A = list(map(int,input().split()))
res = 1
for i in range(N):
    res*=A[i]

if res > 10**18:
    print(-1)
else:
    print(res)



### FIXED CODE ###


import sys

read= sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 1000000007
sys.setrecursionlimit(10**7)


N = int(readline())

A = list(map(int,readline().split()))

if A.count(0) :
    print(0)
else:
    res = 1
    for i in range(N):
        res*=A[i]
        if res > 10**18:
            print(-1)
            exit()

    print(res)
### BUGGY CODE ###

import math

N = int(input())
for i in range(2, 2*N+1, 2):
    C = 0
    for x in range(2, i):
        if 3*x**2 > i:
            break
        for y in range(x, i):
            if x**2 + 2 * y**2 > i:
                break
            z_2 = i - x**2 - y**2
            z = int(math.sqrt(z_2))
            if z**2 == z_2:
                X_2, Y_2, Z_2 = x+y-z, x-y+z, -x+y+z
                if X_2 % 2 == 0 and Y_2 % 2 == 0 and Z_2 % 2 == 0:
                    if X_2 > 0 and Y_2 > 0 and Z_2 > 0:
                        if X_2 == Y_2 == Z_2:
                            C += 1
                        elif X_2 != Y_2 != Z_2:
                            C += 6
                        else:
                            C += 3
    print(C)

### FIXED CODE ###

N = int(input())
A = [0]*(N+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            i = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if i < N+1:
                A[i] += 1
for i in range(1, N+1):
    print(A[i])
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        if 0<= s - x - y <= k:
            count += 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def vanish_golem(pos, n, s, spells):
    for t, d in spells:
        if pos < 0:
            return -1
        if pos >= n:
            return 1

        if s[pos] == t:
            pos += 1 if d == 'R' else -1

    if pos < 0:
        return -1
    elif pos >= n:
        return 1
    else:
        return 0


def search_vanish_golem(n, s, spells, th):
    l = 0
    h = n-1

    while l <= h:
        t = (l+h) // 2
        v = vanish_golem(t, n, s, spells)
        if v < th:
            l = t + 1
        elif v > th:
            h = t - 1

    return l


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

td = [input().split() for _ in range(q)]

l_cnt = search_vanish_golem(n, s, td, 0)
r_cnt = n - search_vanish_golem(n, s, td, 1)

print(n - l_cnt - r_cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
def vanish_golem(pos, n, s, spells):
    for t, d in spells:
        if pos < 0:
            return -1
        if pos >= n:
            return 1

        if s[pos] == t:
            pos += 1 if d == 'R' else -1

    if pos < 0:
        return -1
    elif pos >= n:
        return 1
    else:
        return 0


def search_vanish_golem(n, s, spells, th):
    l = 0
    h = n-1

    while l <= h:
        t = l + (h - l) // 2
        v = vanish_golem(t, n, s, spells)
        if v < th:
            l = t + 1
        else:
            h = t - 1

    return l


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

td = [input().split() for _ in range(q)]

l_cnt = search_vanish_golem(n, s, td, 0)
r_cnt = n - search_vanish_golem(n, s, td, 1)

print(n - l_cnt - r_cnt)
### BUGGY CODE ###

import math
K=int(input())
GCD=[[0]*(K+2) for _ in range(K+2)]

def divable(a,b):
    if a==b:
        return a
    if a<b:
        a,b=b,a
    if a%b>0:
        return 1
    return math.gcd(a,b)

def make_GCD(K):
    for a in range(1,K+1):
        for b in range(1,K+1):
            GCD[a][b]=math.gcd(a,b)            
def gcd3(a,b,c):
    if a<b:
        a,b=b,a
    a=GCD[a][b]
    return GCD[a][c]
make_GCD(K)
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += gcd3(a,b,c)
            
print(ans)

### FIXED CODE ###

K=int(input())
GCD=[[0]*(K+2) for _ in range(K+2)]
import math
def make_GCD(K):
    for a in range(1,K+1):
        for b in range(1,K+1):
            GCD[a][b]=math.gcd(a,b)            
make_GCD(K)

def gcd3(a,b,c):
    a=GCD[a][b]
    return GCD[a][c]
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += gcd3(a,b,c)            
print(ans)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[(input()) for l in range(q)]
if q-k<0:
    for i in range(n):
        print('Yes')
else:
    import collections
    c = collections.Counter(a)
    if c.most_common()[0][1]>=k and q-c.most_common()[0][1]<=k:
        a=int(c.most_common()[0][0])
        for i in range(n):
            if i+1==a:
                print('Yes')
            else:
                print('No')
    else:
        l=([int(i[0]) for i in c.items() if i[1] > q-k])
        #print(l)
        for i in range(n):
            if l.count(i+1)>0:
                print('Yes')
            else:
                print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[(input()) for l in range(q)]
#if q-k<0:
 #   for i in range(n):
  #      print('Yes')
#else:
import collections
c = collections.Counter(a)
for i in range(n):
    #print(k-c[str(i+1)])
    if q-c[str(i+1)]<k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[list(map(int,input().split())) for _ in range(m)]
for b,c in B:A+=[c]*b
print(sum(sorted(A)[-n:]))

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[list(map(int,input().split())) for _ in range(m)]
B.sort(key=itemgetter(1),reverse=True)
C=[]
for b,c in B:
  C+=[c]*b
  if len(C)>=n:break
print(sum(sorted(A+C)[-n:]))
### BUGGY CODE ###

#from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

#@njit
def solve(N, L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                if a+b > L[k]:
                    cnt += 1
    return cnt
print(solve(N, L))

### FIXED CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(L))
### BUGGY CODE ###

import numpy as np
import math

N, M = map(int, input().split())

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

# 1 <= N <= 10^5
# 2 <= M <= 10^9
# 1 <= A <= 10^9

dp = np.zeros(N+1, dtype=int)

dp[N] = 0

for i in reversed(range(N)):
    # N-1 -> 0
    total = 0
    for j in range(i, N):
        total += A[j]
        if total % M == 0:
            dp[i] = 1 + dp[j+1]
            break

# print(dp)
print(sum(dp))


### FIXED CODE ###

import numpy as np
import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

N, M = map(int, input().split())

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

# 1 <= N <= 10^5
# 2 <= M <= 10^9
# 1 <= A <= 10^9

S = []
total = 0
S.append(0)
for i in range(N):
    total = (total + A[i]) % M
    S.append(total)

oS = sorted(S)

count = 0

# print(oS)

cur_val = 0
number = 0
for i in range(0, N+1):
    if oS[i] == cur_val:
        number += 1
    if oS[i] > cur_val or i == N:
        if number >= 2:
            count += int(number * (number - 1) / 2)
        # print(cur_val, number)
        number = 1
        cur_val = oS[i]

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

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



Sn = str(input())
X,Y = map(int, input().split())

xyn = [0]
for c in Sn:
  if c == 'T':
    xyn.append(0)
  else:
    xyn[-1] += 1

Xn = xyn[2::2]
Yn = xyn[1::2]

dp_x = [xyn[0]]
for i in range(len(Xn)):
  dp_xn = []
  for j in dp_x:
    dp_xn = dp_xn + [j+Xn[i], j-Xn[i]]
  dp_x = dp_xn

dp_y = [0]
for i in range(len(Yn)):
  dp_yn = []
  for j in dp_y:
    dp_yn = dp_yn + [j+Yn[i], j-Yn[i]]
  dp_y = dp_yn

if X in dp_x and Y in dp_y:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



Sn = str(input())
X,Y = map(int, input().split())

xyn = [0]
for c in Sn:
  if c == 'T':
    xyn.append(0)
  else:
    xyn[-1] += 1

Xn = xyn[2::2]
Yn = xyn[1::2]

dp_x = {xyn[0]}
for i in range(len(Xn)):
  dp_xn = {}
  for j in dp_x:
    dp_xn[j+Xn[i]] = 1
    dp_xn[j-Xn[i]] = 1
  dp_x = dp_xn

dp_y = {0}
for i in range(len(Yn)):
  dp_yn = {}
  for j in dp_y:
    dp_yn[j+Yn[i]] = 1
    dp_yn[j-Yn[i]] = 1
  dp_y = dp_yn


if X in dp_x and Y in dp_y:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

[N,K]=list(map(int, input().split()))
p=list(map(int, input().split()))

def ex(p,n):
    return (p[n-1]+1)/2

def sum(p,n,K):
    s=0
    for i in range (0,K):
        s=s+ex(p,n+i)
    return s

max=sum(p,1,K)
for i in range (1,N-K+1):
   if sum(p,i+1,K)>=max:
        max=sum(p,i+1,K)
        
print(max)

### FIXED CODE ###

[N,K]=list(map(int, input().split()))
p=list(map(int, input().split()))

def ex(p,n):
    return (p[n]+1)/2


list=[]
s=0
for i in range (0,N):
    s=s+ex(p,i)
    list.append(s)

max=list[K-1]
for i in range (0,N-K):
   if list[i+K]-list[i] >= max:
        max=list[i+K]-list[i]
        
print(max)
### BUGGY CODE ###

import sys
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
towns = [1]
prev = 1
count = 0
while len(towns) == len(set(towns)):
    next = a[prev - 1]
    towns.append(next)
    prev = next
    count += 1
    if count == k:
        print(next)
        sys.exit()
i = towns.index(next)
repeat = towns[i: -1]
unit = len(repeat)
rest = k - len(towns) + 2
print(repeat[(rest % unit) - 1])

### FIXED CODE ###

import sys
from collections import defaultdict
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
towns = [1]
town_dic = defaultdict(lambda : 0)
prev = 1
count = 0
while True:
    next = a[prev - 1]
    count += 1
    if count == k:
        print(next)
        sys.exit()
    if town_dic[next] == 1:
        break
    else:
        town_dic[next] += 1
    towns.append(next)
    prev = next
i = towns.index(next)
repeat = towns[i:]
unit = len(repeat)
rest = k - count + 1
print(repeat[(rest % unit) - 1])
### BUGGY CODE ###

l = []

N = int(input())

for i in range(N):
  x = input()
  if x not in l:
    l.append(x)


print(len(l))



### FIXED CODE ###

myset = set()

N = int(input())

for i in range(N):
  x = input()
  myset.add(x)
    
print(len(myset))
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()

m=int(n/2)
cnt=0
for i in range(L[m-1]+1,L[m]+1):
    
    if len(L[:m])==m:
        cnt+=1
        
print(cnt)

### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()

m=int(n/2)
        
if L[m-1]==L[m]:
    print(0)
else:
    print(L[m]-L[m-1])
### BUGGY CODE ###

n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab0 = []
abn = []
for x in ab:
    if x[0] == 0:
        ab0.append(x[1])
    if x[1] == n-1:
        abn.append(x[0])

res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break

print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        k=j+1
        while (k<n and l[k]< ab):
            k += 1
        count += k-(j+1)
print(count)


### FIXED CODE ###

from bisect import bisect_right

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # bisect_left(a, x): x を a に挿入できる点を返す
        # cの最大値は a+b-1
        k = bisect_right(l, ab-1, j+1, n)
        count += k-(j+1)
print(count)