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

n, sum = map(int, input().split())

for x in range(n+1):
    for y in range(n+1):
        for z in range(n+1):
            if 10000 * x + 5000 * y + 1000 * z == sum and x + y + z == n:
                break
        else:
            continue
        break
    else:
        continue
    break
else:
    x, y, z = -1, -1, -1


print("{} {} {}".format(x, y, z))

### FIXED CODE ###

n, sum = map(int, input().split())

for x in range(n+1):
    for y in range(n+1):
        z = n - x - y        
        if 10000 * x + 5000 * y + 1000 * z == sum and z >= 0:
                break
        else:
            continue
        break
    else:
        continue
    break
else:
    x, y, z = -1, -1, -1


print("{} {} {}".format(x, y, z))
### BUGGY CODE ###

N,K,Q = map(int,input().split())
attend = [K for i in range(N)]
A = 0
for i in range(Q):
	A = int(input())
	for j in range(N):
		if not(j == A-1):
			attend[j]-=1
for i in range(N):
	if(attend[i] <= 0):
		print("No")
	else:
		print("Yes")

### FIXED CODE ###

N,K,Q = map(int,input().split())
attend = [K-Q for i in range(N)]
A = 0
for i in range(Q):
	A = int(input())
	attend[A-1]+=1
for i in range(N):
	if(attend[i] <= 0):
		print("No")
	else:
		print("Yes")
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())
#queries = []
    for _ in range(0, q):
        query = input()
        if len(query) == 1:
     #       queries.append([int(query)])
            s = s[::-1]
        else:
            query = query.split(' ')
            query = [int(query[0]), int(query[1]), query[2]]
#        queries.append(query)
            if query[1] == 1:
                s = query[2] + s
            else:
                s = s + query[2]



#for i in range(0, q):
#    if queries[i][0] == 1:
#        s = s[::-1]
#    else:
#        if queries[i][1] == 1:
#            s = queries[i][2] + s
#        else:
#            s = s + queries[i][2]

    print(s)

main()

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

def main():
    s = input()
    q = int(input())
    is_rev = False
    l = ''
    r = ''
    for _ in range(0, q):
        query = input()
        if len(query) == 1:
            is_rev = not is_rev
        else:
            query = query.split(' ')
            query = [int(query[0]), int(query[1]), query[2]]
            if (query[1] == 1 and is_rev) or (query[1] == 2 and not is_rev):
#                s = s + query[2]
                r += query[2]
            else:
#                s = query[2] + s
                l += query[2]
    if is_rev:
        print(r[::-1] + s[::-1] + l)
    else:
        print(l[::-1] + s + r)

main()
### BUGGY CODE ###

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    ans = 0
    check = 0
    checkmm = 0
    checkm = 0
    a.sort()
    for i in a:
        if i-2 in a:
            checkmm = checkm
        else:
            checkmm = 0

        if i-1 in a:
            checkm = check
        else :
            checkm = 0

        check = a.count(i)


        if ans < check+checkm+checkmm:
            ans = check+checkm+checkmm

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    count = [0]*100000

    for i in a:
        count[i] += 1

    print(max(map(sum,zip(count,count[1:],count[2:]))))


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

from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: x[1] / x[0] - y[1] / y[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

n,a,b = (int(x) for x in input().split())
mod = 10**9+7

def minus(k):
    x,y =1,1
    for i in range(k):
        x*=(n-i)%mod
        y*=(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(a)-minus(b)
if ans<0:
    ans+=mod
print(ans)


### FIXED CODE ###

n,a,b = map(int, input().split())
mod = 10**9+7

def minus(n,k):
    x,y =1,1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(k-i)%mod
    return x*pow(y, mod-2, mod)%mod

ans = pow(2,n,mod)-1-minus(n,a)-minus(n,b)
while ans<0:
    ans+=mod
print(ans)
### BUGGY CODE ###

def submit():
    n, w = map(int, input().split())
    item_max = 100
    val_max = 1000
    col_max = item_max * val_max
 
    # dp[i][j] = item iまでで価値jになるようにした時の最小重み
    dp = [[float('inf') for _ in range(col_max + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 0

    for i in range(1, n + 1):
        wi, vi = map(int, input().split())
        for j in range(col_max + 1):
            if 0 <= j - vi <= col_max:
                dp[i][j] = min(dp[i - 1][j],
                               dp[i - 1][j - vi] + wi)
            else:
                dp[i][j] = dp[i - 1][j]

    ans = 0
    for i in range(col_max + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

submit()
        

### FIXED CODE ###

n, w = map(int, input().split())
item_max = 100
val_max = 1000
col_max = item_max * val_max

# dp[i][j] = item iまでで価値jになるようにした時の最小重み
dp = [[float('inf') for _ in range(col_max + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    wi, vi = map(int, input().split())
    for j in range(1, col_max + 1):
        if j >= vi:
            dp[i][j] = min(dp[i - 1][j],
                            dp[i - 1][j - vi] + wi)
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(col_max + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)
### BUGGY CODE ###

from collections import deque
import copy
n,m = map(int,input().split())

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1
used2 = [0]*n
used2[root]=1
#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            used2[e]=1
            res[e]=z+1
            tank2.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
while c != n:
    tank = tank2
    tank2 = deque([])
    used = copy.deepcopy(used2)
    while len(tank)!=0:
        f(tank.popleft())
    c += len(tank2)
    
for i in range(n):
    print(res[i])


### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1

#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            res[e]=z+1
            tank2.append(e)
            usedtank.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
usedtank = []
while c != n:
    tank = tank2
    tank2 = deque([])
    usedtank = []
    while len(tank)!=0:
        f(tank.popleft())
    for usede in usedtank:
        used[usede]=1
    c += len(tank2)
    
for i in range(n):
    print(res[i])
### BUGGY CODE ###

n=int(input())
i=1
facts = []
ans = 0
Number  =n
for i in range(2, Number + 1):
    if(Number % i == 0):
        isprime = 1
        for j in range(2, (i //2 + 1)):
            if(i % j == 0):
                isprime = 0
                break
        if (isprime == 1):
            facts.append(i)

facts = sorted(facts)
for i in range(len(facts)):
    cnt = 1
    while(n >= facts[i]**cnt):
        if(n%(facts[i]**cnt)==0):
            n//=(facts[i]**cnt)
            ans+=1
        cnt+=1
print(ans)



### FIXED CODE ###

n=int(input())
i=1
facts = []
ans = 0
Number  =n
import math 
def factorize(n): 
    count = 0
    while ((n % 2 > 0) == False):  
        n >>= 1;  
        count += 1
    if (count > 0): 
        facts.append(2)
    for i in range(3, int(math.sqrt(n)) + 1): 
        count = 0
        while (n % i == 0):
            count += 1 
            n = int(n / i)
        if (count > 0): 
            facts.append(i)
        i += 2
    if (n > 2): 
        facts.append(n)
factorize(n)
facts = sorted(facts)
for i in range(len(facts)):
    cnt = 1
    while(n >= facts[i]**cnt):
        if(n%(facts[i]**cnt)==0):
            n//=(facts[i]**cnt)
            ans+=1
        cnt+=1
print(ans)
### BUGGY CODE ###

#とりあえずKを全探索
def 解():
    N,K=[int(_) for _ in input().split()]
    aA=[int(_) for _ in input().split()]
    aD = [0]*40
    for a in aA:
        a = "{:b}".format(int(a))[::-1]
        for i in range(len(a)):
            if a[i] == "1":
                aD[i] += 1
    dsA = set(aA)
    iL = 0
    for i in range(40):
        if 0 < aD[i]:
            iL = i
    iL +=1
    def calcTotal(iK,aD,N,iL):
        sK = "{:b}".format(int(iK))[::-1]
        iLK = len(sK)
        if iL > iLK:
            sK +="0"*(iL-iLK)
        else:
            iL = iLK
        iC = 0
        for i in range(iL):
            if sK[i] == "0":
                iC += (2 ** i) *  aD[i]
            else:
                iC += (2 ** i) * (N - aD[i])
        return iC
    print(max(calcTotal(i,aD,N,iL) for i in set(range(K+1)) - dsA | {0}))
解()


### FIXED CODE ###

#場合分けがつらい
def 解():
    N,K=[int(_) for _ in input().split()]
    aD =[0]*40
    aA=[int(_) for _ in input().split()]
    iL = 0
    for i in range(40):
        m = 2**i
        aD[i]=sum((_ & m) for _ in aA)
        if aD[i]:
            iL = i
    iLK = len(bin(K))-3
    iML = max(iL,iLK)
    dp = [[0]*2 for _ in range(2)]
    #[x][0] Kに沿う
    #[x][0] Kに沿わない最大
    for i in range(iML,-1,-1):
        ib = i%2 #桁%2 dp
        inb = 0 if ib else 1 #次のdp
        i0 = aD[i] #反転しない
        i1 = (2**i)*N-i0 #反転する
        iM = max(i0,i1) #選べるとき
        bL = i < iLK #Kより長い
        if (K>>i)&1:
            dp[inb][1] = dp[ib][1] + i1
            dp[inb][0] = max(dp[ib][1] + i0 ,dp[ib][0]+(iM if bL else i0))
        else:
            dp[inb][1] = dp[ib][1] + i0
            dp[inb][0] = dp[ib][0] + (iM if bL else i0)
    print(max(dp[inb]))
解()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = []
for i in range(n):
    b = sorted(a.copy(), reverse=True)
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(a.copy(), reverse=True)
for i in range(n):
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

n = int(input())
A = [list(map(int, list('{:020b}'.format(a))))
     for a in map(int, input().split())]

ans = 0
R = -1
X = [0]*20
for L in range(n):
    if R < L:
        R += 1
        for i in range(20):
            X[i] += A[R][i]

    while R+1 < n and all(x+y != 2 for x, y in zip(X, A[R+1])):
        for i in range(20):
            X[i] += A[R+1][i]
        R += 1
    ans += R-L+1
    for i in range(20):
        X[i] -= A[L][i]
print(ans)

### FIXED CODE ###

n = int(input())
A = [list(map(int, list('{:020b}'.format(a))))
     for a in map(int, input().split())]

ans = 0
R = -1
X = [0]*20
for L in range(n):
    if R < L:
        R += 1
        for i in range(20):
            X[i] += A[R][i]

    while R+1 < n and all(x+y != 2 for x, y in zip(X, A[R+1])):
        for i in range(20):
            X[i] += A[R+1][i]
        R += 1
    ans += R-L+1
    for i in range(20):
        X[i] -= A[L][i]
print(ans)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
ans = 0
from itertools import combinations

for i,j,k in combinations(L, 3):
    res = sorted([i,j,k])
    if sum(res[:2]) > res[2]:
        ans += 1

print(ans)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
L = sorted(list(map(int, input().split())))
#print(L)
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
        #print(i,j,bisect_left(L,L[i]+L[j]),(j+1))
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
r = 0
qn = []*3
left =''
right = ''

for i in range(q):
    qn = input().split()
    if qn[0] == '1':
        r += 1
    elif qn[0] == '2':
        if qn[1] == '1' and r%2 == 0:
            left = qn[2] + left
        elif qn[1] == '1' and r%2 == 1:
            right += qn[2]
        elif qn[1] == '2' and r % 2 == 0:
            right += qn[2]
        elif qn[1] == '2' and r % 2 == 1:
            left = qn[2] + left

ans = left + s + right

if r%2 == 1:
    ans = ans[::-1]

print(ans)

### FIXED CODE ###

s = input()
q = int(input())
r = 0
qn = []*3
left =''
right = ''

for i in range(q):
    qn = input().split()
    if qn[0] == '1':
        r += 1
    elif qn[0] == '2':
        if qn[1] == '1' and r%2 == 0:
            left = qn[2] + left
        elif qn[1] == '1' and r%2 == 1:
            right += qn[2]
        elif qn[1] == '2' and r % 2 == 0:
            right += qn[2]
        elif qn[1] == '2' and r % 2 == 1:
            left = qn[2] + left

ans = left + s + right

if r%2 == 1:
    ans = ans[::-1]

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

from bisect import bisect

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

G = [[] for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L].append(R)

for i in range(N+1):
  G[i].sort()

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += bisect(G[i], q)
  print(ans)

### FIXED CODE ###

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

G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L][R] += 1

for i in range(N+1):
  for j in range(1, N+1):
    G[i][j] += G[i][j-1]

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += G[i][q]
  print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append(S[-1]+a)   #累積和

ans=0
for l in range(N):
    for r in range(l+1,min(l+K,N+1)):
        if (S[r]-S[l])%K==0:
            ans+=1
print ans

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,K=map(int, sys.stdin.readline().split())
if K==1:
    print 0
    quit()
A=map(int, sys.stdin.readline().split())
A=map(lambda a: (a-1)%K, A)

S=[0]
for a in A:
    S.append( (S[-1]+a)%K )   #累積和

d=dict()    #要素：要素の数を持つ

ans=0
for i in range(N+1):
    x=S[i]%K
    if i==0:
        d[x]=1
    else:
        if x in d:
            ans+=d[x]   #自分より前に同じ出現した、自分と同じ要素の数を答えに追加
            d[x]+=1
        else:
            d[x]=1      
        if 0<=i-K+1:
            x_head=S[i-K+1]%K  #長さK-1の範囲で配列Sを見るため、１つ進んだら一番先頭の要素を辞書から削除する
            d[x_head]-=1

print ans
### BUGGY CODE ###

from collections import defaultdict, Counter

def main():
  n, *A = map(int, open(0).read().split())
  cnt = defaultdict(int, Counter(A))
  dset = defaultdict(set)
  l = len(A)
  for i in cnt:
    for j in range(1, int(i ** 0.5) + 1):
      if not i % j:
        dset[i].add(j)
        dset[i].add(i // j)
  res = [l - sum([cnt[j] for j in dset[i]]) == n - 1 for i in A]
  print(sum(res))
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

from collections import defaultdict, Counter

def main():
  n, *A = map(int, open(0).read().split())
  A.sort()
  n = A[-1]
  isPrime = [True] * (n + 1)
  prep = 0
  for i in A:
    if prep == i:
      isPrime[prep] = False
      continue
    if isPrime[i]:
      for j in range(i * 2, n + 1, i):
        isPrime[j] = False
    prep = i

  prep = res = 0
  for i in A:
    if prep == i:
      continue
    if isPrime[i]:
      res += 1
    prep = i
  print(res)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import math

N = int(input())
a = [int(i) for i in input().split()]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

koubai = 1
for i in range(N):
    koubai = lcm(koubai, a[i])

f = [0 for i in range(koubai)]

for i in range(len(f)):
    for j in range(N):
        f[i] += i % a[j]

print(max(f))

### FIXED CODE ###

import math

N = int(input())
a = [int(i) for i in input().split()]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

koubai = 1
for i in range(N):
    koubai = lcm(koubai, a[i])

# f = [0 for i in range(koubai)]

# for i in range(len(f)):
#     for j in range(N):
#         f[i] += i % a[j]

ans = 0
for i in range(N):
    ans += (koubai-1) % a[i]

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

import heapq
from collections import deque
n,m=map(int,input().split())
A=list(map(int,input().split()))
#print(A)
for i in range(n):
    A[i]*=-1
#print(A)

for i in range(m):
    heapq.heapify(A)
    x=heapq.heappop(A)
    #print(x,A)
    if x%2==0:
        x//=2
    else:
        x=x//2 +1
    heapq.heappush(A,x)
    #print(A)
ans=-1*sum(A)
print(ans)

### FIXED CODE ###

import heapq
from collections import deque
n,m=map(int,input().split())
A=list(map(int,input().split()))

for i in range(n):
    A[i]*=-1
heapq.heapify(A)

for i in range(m):
    x=heapq.heappop(A)
    if x%2==0:
        x//=2
    else:
        x=x//2 +1
    heapq.heappush(A,x)

ans=-1*sum(A)
print(ans)
### BUGGY CODE ###

#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

# 複数個の数値を、intの配列として取得
A = list(map(int, input().split()))
A.sort()

for i in range(M):
    d = A.pop(-1)/2
    bisect.insort_left(A,d)

ans=0
for i in range(N):
    ans+=math.floor(A[i])

print(ans)

### FIXED CODE ###

#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

# 複数個の数値を、intの配列として取得
A = list(map(int, input().split()))
A = list(map(lambda x: x * (-1),A))

heapq.heapify(A)
for i in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A,x/2)

ans=0
for a in A:
    ans+=math.floor(-a)

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

from collections import Counter
from collections import defaultdict

def fact(n):
    fact = 1
    for i in range(1,n+1):
        fact *= i
    return fact

def combinations_count(n,r):
    return fact(n) // (fact(n - r) * fact(r))

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = Counter(A)
    d = defaultdict(lambda:-1)
    for i in range(N):
        ans = 0
        if d[A[i]] != -1:
            ans += d[A[i]]
        else:
            c[A[i]] -= 1
            v = list(c.values())
            for j in v:
                if j >= 2:
                    ans += combinations_count(j, 2)
            d[A[i]] = ans
            c[A[i]] += 1
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = Counter(A)
    comb = 0
    for i in c.values():
        if i >= 2:
            comb += i*(i-1)//2
    for i in range(N):
        print(comb - (c[A[i]] - 1))

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

N,K=map(int,input().split())
dice = list(map(int, input().split()))#dic=[]

kitai=[]
def calc(n):
    return (n+1)/2

data = list(map(calc, dice))
s=[]

for j in range(N-K+1):
    su=sum(data[j:j+K])
    s.append(su)
print(max(s))


### FIXED CODE ###

N,K=map(int,input().split())
dice = list(map(int, input().split()))
a=sum(dice[0:K])

l = [a]
for i in range(1,N-K+1):
    a = a - dice[i-1] + dice[K-1+i]
    l.append(a)
print((max(l)+K)/2)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
P =[]
max_l = 0
max_v = 0
P = list(map(int, input().split()))
for i, p in enumerate(P):
  if i <= N-K:
    #print(P[i:K+i])
    if max_v < sum(P[i:K+i]):
      max_v = sum(P[i:K+i])
      
      max_l = P[i:K+i]
#print(max_v)
ans = 0
for l in max_l:
  ans += (l+1)/2
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
P = list(map(int, input().split()))
PP = [(i+1)/2 for i in P]
ans = 0
ttl = 0
for i,p in enumerate(PP):
    ttl += p
    if i >= k:
        ttl -= PP[i-k]
    ans = max(ttl, ans)
print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    # dp[i][i] を a[i] で初期化
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return(dp[0][-1])

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f(n, a))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, a):
    dp = [[0] * n for _ in range(n)]
    # dp[i][i] を a[i] で初期化
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(i + 1, n):
            r = a[i] - dpi1[j]
            l = a[j] - dpi[j - 1]
            dp[i][j] = r if r > l else l
            # dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return(dp[0][-1])

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

ad=[[],[]]
count=0
s=input()
q=int(input())
for i in range(q):
    t=input().split()
    if t[0]=='1':
        count+=1
        ad[0].reverse()
        ad[1].reverse()
        ad=[ad[1],ad[0]]
    elif t[1]=='1':
        ad[0].insert(0,t[2])
    else:
        ad[1].append(t[2])

if count%2==0:
    print(''.join(ad[0])+s+''.join(ad[1]))
else:
    print(''.join(ad[0])+s[::-1]+''.join(ad[1]))

### FIXED CODE ###

s=[input()]
q=int(input())
turn=True
l=""
for i in range(q):
    qq=input().split()
    if qq[0]=='1':
        turn=not turn
    else:
        if turn==bool(int(qq[1])-2):
            l+=qq[2]
        else:
            s.append(qq[2])

text=l[::-1]+"".join(s)
print(text if turn else text[::-1])
### BUGGY CODE ###

s = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


divisors = make_divisors(s)

for d in divisors:
    if d <= 10e9 and s/d <= 10e9:
        x2 = d
        y3 = s//d

print("0 0 {} 0 0 {}".format(x2, y3))


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

N, Q = input().split(' ')
N = int(N)
Q = int(Q)

S = input()
AC ='AC'

indices = []
for i in range(Q):
    l_i, r_i = input().split(' ')
    l_i = int(l_i)
    r_i = int(r_i)
    indices.append((l_i, r_i))

for idx in indices:
    print(S[idx[0]-1:idx[1]].count(AC))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l_i, r_i = map(int, input().split())
    print(t[r_i-1] - t[l_i-1])