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

import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
k = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if L:
            t, X, f = L.pop()
            if t <= D:
                if f == 1:
                    Xs.add(X)
                else:
                    Xs.remove(X)
            else:
                L.append((t, X, f))
                break
        else:
            break
    if Xs:
        print(min(Xs))
    else:
        print("-1")

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N, Q = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, 1, X)
    L[2 * i + 1] = (T-X, -1, X)
for i in range(Q):
    D = int(input())
    L[2 * N + i] = (D, 2, 0)
L.sort()

Xs = set([])
XH = []
heapq.heapify(XH)
for t, f, X in L:
    if f == 1:
        Xs.add(X)
        heapq.heappush(XH, X)
    elif  f == -1:
        Xs.remove(X)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")
### BUGGY CODE ###

import collections
n = int(input())
l = list(str(input()) for _ in range(n))
d = [{} for _ in range(n)]

for m, a in enumerate(l):
    for p in range(10):
        d[m][a[p]] = a.count(a[p])
cnt = 0
for i, j in enumerate(d):
    for k in range(i+1, len(d)):
        if j == d[k]:
            cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())
s = [input() for i in [0]*N]
words = {}
cnt = 0
for i in s:
    i = "".join(sorted(i))
    time = words.get(i,0)
    cnt += time
    words[i] = time + 1
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
m = 10 ** 9 + 7
for i in range(N - 1):
    for j in range(i + 1, N):
        ans += A[i] * A[j]
        ans %= m
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(a ** 2 for a in A)
m = 10 ** 9 + 7
ans = int((sum(A) ** 2) // 2)
ans %= m
ans -= int(sum(B) // 2)
ans %= m
print(ans)
### BUGGY CODE ###

n = int(input())
num = [int(input()) for i in range(n)]

gra = [1]*n


for i in range(1,n):
    Max = 1
    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(max(gra))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import bisect
#D2
n = int(input())
a = [int(input()) for j in range(n)]
 
dp = [a[0]]
for i in range(1,n):
    if dp[-1] < a[i]:
        dp.append(a[i])
        #print(0,dp)
 
    else:
        dp[bisect.bisect_left(dp, a[i])] = a[i]
        #print(1,bisect.bisect_left(dp, a[i]),dp)
print(len(dp))
### BUGGY CODE ###

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

count = [0]*(10**5+1)
for i in range(len(A)):
  count[A[i]] += 1

A = list(set(A))
for i in range(Q):
  B, C = map(int, input().split())
  count[C] += count[B]
  count[B] = 0
  ans = 0
  for i in range(10**5+1):
    ans += count[i] * i
  print(ans)
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = sum(A)
count = [0]*(10**5+1)
for i in range(len(A)):
  count[A[i]] += 1

A = list(set(A))
for i in range(Q):
  B, C = map(int, input().split())
  S = S - B*count[B] + C*count[B]
  count[C] += count[B]
  count[B] = 0
  print(S)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, K = map(int, input().split())
    N_1 = [set() for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        N_1[a].add(b)
        N_1[b].add(a)
        
    checked = set()
    q = {1}
    res = 1
    while q:
        n = q.pop()
        q.update(set.difference(N_1[n], checked))
        N_2 = set.union(N_1[n], *[N_1[m] for m in N_1[n]]) - {n}
        fixed = len(set.intersection(N_2, checked))
        res *= K - fixed
        checked.add(n)
        if res < 0:
            return str(0)
        else:
            res %= 10**9+7
    return str(res)


if __name__ == '__main__':
    print(solve())



### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, K = map(int, input().split())
    N_1 = [{1},{0}]+[set() for _ in range(N-1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        N_1[a].add(b)
        N_1[b].add(a)
    checked, q = set(), {0}
    res = 1
    while q:
        n = q.pop()
        checked.add(n)
        q.update(set.difference(N_1[n], checked))
        K_ = K-min(2,n)
        for i in range(len(N_1[n])-(n>0)):
            if K_ == i:
                return str(0)
            res = (res*(K_-i))%(10**9+7)
    return str(res)
if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

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

ans = 0
for i in range(n-2):
    for j in range(i+2, n):
        if a.count(a[i]) < 2:
            continue
        if a[j:n].count(a[j]) < 2:
            continue
        ans = max(ans, a[i] * a[j])

print(ans)


### FIXED CODE ###

from collections import Counter

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

s = sorted(Counter(a).items(), reverse = True)


count = 0
ans = 0
for i, j in s:
        if count == 2:
            break
        if count == 1 and j >= 2:
            ans *= i
            count += 1
        if count == 0:
            if j >= 4:
                ans = i**2
                count += 2
            elif j >= 2:
                ans = i
                count += 1
print(ans)
### BUGGY CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]

  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub == 0:
        dp[i + 1][j] += 2 ** (i)
      if sub > 0 and dp[i][sub]:
        dp[i + 1][j] += dp[i][sub]
  #print(dp)
  print(dp[length][target] % 998244353)
  
solve(N, S, A)

### FIXED CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
solve(N, S, A)
### BUGGY CODE ###

N = int(input())
names = []
words = {}
for i in range(N):
    name = input()
    if name not in names:
        words[name] = 1
        names.append(name)
    elif name in names:
        words[name] += 1
        
max_name_list = [nm[0] for nm in words.items() if nm[1] == max(words.values())]
max_name_list = sorted(max_name_list)

for i in range(len(max_name_list)):
    print(max_name_list[i])

### FIXED CODE ###

N = int(input())
words = {}
for i in range(N):
  name = input()
  if name not in words:
    words[name] = 1
  elif name in words:
    words[name] += 1
    
res_name = []
Max = max(words.values())
for i in words.keys():
  if words[i] == Max:
    res_name.append(i)
res_name = sorted(res_name)
for i in res_name:
  print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

# 昔同じ問題を atcoder で見た？
n = int(input())
edges = []
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    edges.append((a, b))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]
# print(edges)
# print(paths)
colors = {}  # (a->b) 1 とか
current = 1
biggest = 1
def f(current, prev, prev_color):
    global biggest
    color = 0
    for vertex in paths[current]:
        if vertex == prev:
            continue
        color += 1
        if color == prev_color:
            color += 1
        biggest = max(biggest, color)
        colors[(current, vertex)] = color
        f(vertex, current, color)
f(1, None, None)

print(biggest)
for a, b in edges:
    print(colors[(a, b)])
# TLE のみ？

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

# 昔同じ問題を atcoder で見た？
n = int(input())
edges = []
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    edges.append((a, b))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]
# print(edges)
# print(paths)
colors = {}  # (a->b) 1 とか
current = 1
biggest = 1
def f(current, prev, prev_color):
    global biggest
    color = 0
    for vertex in paths[current]:
        if vertex == prev:
            continue
        color += 1
        if color == prev_color:
            color += 1
        biggest = max(biggest, color)
        colors[(current, vertex)] = color
        f(vertex, current, color)
f(1, None, None)

print(biggest)
for a, b in edges:
    print(colors[(a, b)])
# pypy3
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys


def _i(): return int(sys.stdin.readline().strip())


def main():
    x = _i()
    i = 0
    while True:
        i5 = i ** 5
        if x > 2 * i5:
            i += 1
            continue
        for j in range(-i+1, i+1):
            j5 = j ** 5
            ij = i5 - j5
            if ij == x:
                return f"{i} {j}"
            if ij > x:
                break
        i += 1


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys


def _i(): return int(sys.stdin.readline().strip())


def main():
    x = _i()
    sq = [i**5 for i in range(120)]
    for i in range(1, 120):
        i5 = sq[i]
        for j in range(-i, i):
            j5 = sq[j] if j >= 0 else -sq[-j]
            if i5-j5 == x:
                return f"{i} {j}"


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

N = int(input())

ans = 0
for a in range(1, N+1):
    b = 1
    while a * b < N:
        ans += 1
        b += 1

print(ans)


### FIXED CODE ###

N = int(input())

ans = 0
for a in range(1, N+1):
    x = N // a

    if N % a == 0:
        ans += x - 1
    else:
        ans += x

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

n = int(input())
a = [int(x) for x in input().split()]

ans = 1
for aa in a:
    ans *= aa

print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

def main():
    _ = int(input())
    a = [int(x) for x in input().split()]

    if 0 in a:
        print(0)
        return

    ans = 1
    for aa in a:
        ans *= aa
        if ans > 10**18:
            print(-1)
            return

    print(ans)


main()
### BUGGY CODE ###

#!/usr/bin/env python3

n=int(input())  #->n=5
ai=list(map(int,input().split()))  #->nl=[1,2,-,n]

temp = 0
for i in range(n-1):
    for j in range(i+1,n):
        temp = temp + ai[i]*ai[j]
        temp = temp % (10**9+7)

print(temp)



### FIXED CODE ###

#!/usr/bin/env python3

n=int(input())  #->n=5
a=list(map(int,input().split()))  #->nl=[1,2,-,n]
mod=int(1e9+7)

# Accumulate
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):  pre[i]=pre[i-1]+a[i]
ans=0
for i in range(1,n):  ans=(ans+(a[i-1]*(pre[n-1]-pre[i-1]))%mod)%mod
print(ans)
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
y = 0
x = 0
for i in range(n-1):
  if x > y:
        y = x
  x = 0
  for j in range(n-i-1):
    if h[i+j] >= h[i+j+1]:
      x += 1
    else:
      break
print(y)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
y = 0
x = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
      x += 1
      if x > y:
        y = x
  else:
      x = 0
print(y)
### BUGGY CODE ###

x = int(input())
flag = 0
if x == 1:
  print(1, 0)
else:
  for i in range(x+1):
    a_0 = 0
    if i**5 >= x:
      a_0 = i
      break
  for a in range(a_0-1, x+1):
    if flag == 1:
      break
    for b in range(x+1):
      if a**5 - b**5 == x:
        print(a, b)
        flag += 1
        break
      elif a**5 + b**5 == x:
        print(a, -1*b)
        flag += 1
        break

### FIXED CODE ###

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

flag = 0
a_s = 0
if x == 1:
  print(1, 0)
else:
  l = make_divisors(x)
  for a in range(a_s, x+1):
    if flag == 1:
      break
    for b_a in l:
      if b_a <= a:
        b = a - b_a
        if a**5 - b**5 == x or a**5 + b**5 == x:
          flag += 1
          print(a, b)
          break
      if b_a > a:
        b = b_a - a
        if a**5 + b**5 == x:
          flag += 1
          print(a, -b)
          break
### BUGGY CODE ###

n,a=map(int,input().split())
x=[0]+list(map(int,input().split()))
dp=[[[0 for k in range(2509)] for j in range(55)] for i in range(55)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*a+1):
            if k<x[i]:
                dp[i][j][k]=dp[i-1][j][k]
            if k>=x[i] and j>=1:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
ans=0
for t in range(1,n+1):
    ans+=dp[n][t][a*t]
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,a=map(int,input().split())
x=[0]+list(map(int,input().split()))
su=sum(x)
maxi=max(x)
dp=[[[0 for k in range(maxi*n+1)] for j in range(51)] for i in range(51)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(maxi*j+1):
            if k<x[i]:
                dp[i][j][k]=dp[i-1][j][k]
            if k>=x[i] and j>=1:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
ans=0
for t in range(1,n+1):
    if a*t<=su:
        ans+=dp[n][t][a*t]
    else:
        break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

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

ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)

cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x


# print(cnt)


def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)


d(1, -1)
print(*cnt[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)

cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x


# print(cnt)


def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)


d(1, -1)
print(*cnt[1:])
### BUGGY CODE ###

n, m = map(int, input().split())
a = [list(map(int,input().split())) for i in range(m)]
p = [[] for i in range(n)]
for i,j in sorted(a, key=lambda x:x[1]): p[i-1].append(j)
for i,j in a:
	high6 = str(i).zfill(6)
	low6 = str(p[i-1].index(j)+1).zfill(6)
	print(high6+low6)

### FIXED CODE ###

from sys import stdin
input = stdin.readline
n, m = map(int, input().split())

ans = sorted([list(map(int, input().split()))+[i] for i in range(m)], key=lambda x:x[1])

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

for i in sorted(ans,key=lambda x:x[2]): print("%06d%06d" % (i[0],i[1]))
### BUGGY CODE ###

N = int(input())
*P, = map(int, input().split())

N += 1
data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

E = [(v, i) for i, v in enumerate(P)]
E.sort(reverse=1)

add(1, 1)
add(N+1, 1)

ans = 0
for v, i in E:
    k = get(i+2)
    l1 = lower_bound(k-2)
    l0 = lower_bound(k-1)
    r0 = lower_bound(k)
    r1 = lower_bound(k+1)
    if l0 > 1:
        ans += (l0-l1) * (r0 - (i+2)) * v
    if r0 < N+2:
        ans += (r1-r0) * (i+2 - l0) * v
    add(i+2, 1)
print(ans)

### FIXED CODE ###

N = int(input())
*P, = map(int, input().split())

N += 1
data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

E = [(v, i) for i, v in enumerate(P)]
E.sort(reverse=1)

add(1, 1)
add(N+1, 1)

ans = 0
for v, i in E:
    k = get(i+2)
    l1 = lower_bound(k-2)
    l0 = lower_bound(k-1)
    r0 = lower_bound(k)
    r1 = lower_bound(k+1)
    if l0 > 1:
        ans += (l0-l1) * (r0 - (i+2)) * v
    if r0 < N+2:
        ans += (r1-r0) * (i+2 - l0) * v
    add(i+2, 1)
print(ans)
### BUGGY CODE ###

def solve(S, Q):
    flg = 0
    for i in range(Q):
        que = input().split()
        if len(que) == 1:
            flg += 1
        else:
            if flg % 2 == 0:
                if que[1] == '1':
                    S = que[2] + S
                elif que[1] == '2':
                    S = S + que[2]
            elif flg % 2 == 1:
                if que[1] == '1':
                    S = S + que[2]
                elif que[1] == '2':
                    S = que[2] + S
    if flg % 2 == 1:
        S = S[::-1]
    print(S)

def main():
    S = input()
    Q = int(input())
    solve(S, Q)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def solve(S, Q):
    S = deque(S)
    flg = 0
    for _ in range(Q):
        que = input().split()
        if len(que) == 1:
            flg += 1
        else:
            if flg % 2 == 0:
                if que[1] == '1':
                    S.extendleft(que[2])
                elif que[1] == '2':
                    S.extend(que[2])
            elif flg % 2 == 1:
                if que[1] == '1':                 
                    S.extend(que[2])
                elif que[1] == '2':                
                    S.extendleft(que[2])
    S = ''.join(S)
    if flg % 2 == 1:
        S = S[::-1]
    print(S)

def main():
    S = input()
    Q = int(input())
    solve(S, Q)

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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
N, K =LI()
A = LI()
F = LI()
A.sort(reverse=True)
F.sort()

xupper = max(A)*max(F)
xlower = int(0)
xcandi = xupper//2

sumA = sum(A)

while (True):
#    print(xlower,xupper, xcandi)
    k = int(0)
    for i in range(N):
        k += max((A[i]*F[i]-xcandi+(F[i]-1))//F[i],0)
#    print(k)

    if k>K:
        xlower = xcandi
        xcandi = ((xcandi + xupper) // 2)+1
    else:
        if xupper-xlower<=1:
            ans = xcandi
            break
        else:
            xupper = xcandi
            xcandi = (xcandi + xlower) // 2

print(ans)

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
N, K =LI()
A = LI()
F = LI()
A.sort(reverse=True)
F.sort()

xupper = max(A)*max(F)
xlower = int(0)
xcandi = xupper//2

sumA = sum(A)

while (True):
#    print(xlower,xupper, xcandi)
    k = int(0)
    for i in range(N):
        k += max((A[i]*F[i]-xcandi+(F[i]-1))//F[i],0)
#    print(k)

    if k>K:
        xlower = xcandi
        xcandi = ((xcandi + xupper) // 2)+1
    else:
        if xupper-xlower<=1:
            ans = xcandi
            break
        else:
            xupper = xcandi
            xcandi = (xcandi + xlower) // 2

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

def main():
  ans = [-1, -1, -1]
  N, Y = map(int, input().split())
  for a in range(N+1):
    for b in range(N+1):
      for c in range(N+1):
        if 1000*a + 5000*b + 10000*c == Y and a + b + c == N:
          ans = [c, b, a]
  print(*ans)
if __name__ == "__main__":
  main()


### FIXED CODE ###

def main():
  ans = [-1, -1, -1]
  N, Y = map(int, input().split())
  for i in range(N+1):
    for j in range(N+1-i):
      if 1000*i + 5000*j + 10000*(N-i-j) == Y:
        ans = [N-i-j, j, i]
  print(*ans)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N,M = map(int, input().split())
A = list(map(int,input().split()))
A.sort()
max = 0 

for i in range(M):
    B,C = map(int, input().split())
    for j in range(B) :
        if  C >= A[j] : 
            A[j] = C
        else :
            continue
    A.sort()
sum = 0 
for i in range(N):
    sum += A[i] 

print(sum)

### FIXED CODE ###

import collections
N,M = map(int, input().split())
A = list(map(int,input().split()))
D = collections.Counter(A)

A.sort()
max = 0 

for i in range(M):
    B,C = map(int, input().split())
    D[C] += B  

D = sorted(D.items(), key=lambda x:x[0],reverse=True)

sum = 0 
count = 0 
for k,v in D:
    if N > v : 
        sum += k * v
        N -= v 
    else : 
        sum += k * N 
        break 
print(sum)
### BUGGY CODE ###

h, n = map(int, input().split())
magic = [tuple(map(int, input().split())) for _ in range(n)]
#magic = [list(map(int, input().split())) for _ in range(n)]

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

print(dp[-1])

### FIXED CODE ###

h, n = map(int, input().split())
magic = [tuple(map(int, input().split())) for _ in range(n)]
#magic = [list(map(int, input().split())) for _ in range(n)]

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        #print(d, c, dp)

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

t = input().split(" ")

N = int(t[0])
K = int(t[1])

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

ans = 0
a =0

for i in range(len(p)):
    #a = list(range(1,p[i]+1))
    #print(a)
    p[i] = sum(list(range(1,p[i]+1)))/p[i]
    
    a += p[i]
    
    if i >= K-1:
        
        if i >= K:
            a += -(p[i-K])
        if a > ans:
            ans = a

print(ans)

    
    






### FIXED CODE ###

t = input().split(" ")

N = int(t[0])
K = int(t[1])

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

ans = 0
a =0

for i in range(len(p)):
    #a = list(range(1,p[i]+1))
    #print(a)
    p[i] = ((p[i]*(p[i]+1))/2)/p[i]
    a += p[i]
    
    if i >= K-1:
        
        if i >= K:
            a += -(p[i-K])
        if a > ans:
            ans = a

print(ans)