Problem:
 Score : 500 points    Problem Statement There are N cards. The i -th card has an integer A_i written on it.
For any two cards, the integers on those cards are different.  Using these cards, Takahashi and Aoki will play the following game:   Aoki chooses an integer x .  Starting from Takahashi, the two players alternately take a card. The card should be chosen in the following manner:  Takahashi should take the card with the largest integer among the remaining card.  Aoki should take the card with the integer closest to x among the remaining card. If there are multiple such cards, he should take the card with the smallest integer among those cards.    The game ends when there is no card remaining.   You are given Q candidates for the value of x : X_1, X_2, ..., X_Q .
For each i ( 1 \leq i \leq Q ), find the sum of the integers written on the cards that Takahashi will take if Aoki chooses x = X_i .      Constraints  2 \leq N \leq 100  000  1 \leq Q \leq 100  000  1 \leq A_1 < A_2 < ... < A_N \leq 10^9  1 \leq X_i \leq 10^9 ( 1 \leq i \leq Q )  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  Q  A_1  A_2  ...  A_N  X_1  X_2  :  X_Q       Output Print Q lines. The i -th line ( 1 \leq i \leq Q ) should contain the answer for x = X_i .        Sample Input 1 5 5
3 5 7 11 13
1
4
9
10
13      Sample Output 1 31
31
27
23
23  For example, when x = X_3(= 9) , the game proceeds as follows:   Takahashi takes the card with 13 .  Aoki takes the card with 7 .  Takahashi takes the card with 11 .  Aoki takes the card with 5 .  Takahashi takes the card with 3 .   Thus, 13 + 11 + 3 = 27 should be printed on the third line.       Sample Input 2 4 3
10 20 30 40
2
34
34      Sample Output 2 70
60
60

Solution (Python):
import bisect
N,Q = map(int,input().split())
A = list(map(int,input().split()))
X = [int(input()) for i in range(Q)]
A.reverse()

cums = [0]
cums_e = [0]
for i,a in enumerate(A):
    cums.append(cums[-1] + a)
    cums_e.append(cums_e[-1] + (0 if i%2 else a))

borders = []
scores = []
for i in range(1,N//2+N%2):
    b = (A[i] + A[2*i])//2 + 1
    borders.append(b)
    s = cums[i] + cums_e[-1] - cums_e[2*i]
    scores.append(s)
if N%2:
    scores.append(cums[N//2+1])
else:
    scores.append(cums[N//2])

borders.reverse()
scores.reverse()

ans = []
for x in X:
    i = bisect.bisect(borders, x)
    ans.append(scores[i])
print(*ans, sep='\n')

Solution (Python):


 
import bisect
 
N,Q=map(int,input().split())
 
A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0
 
for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]
 
X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  
 




y=N//2-1
ans=[0]*Q
for x,i in X:
  
  while y<=N-1 and x>A[y]:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  
  ans[i]+=Asum[N-1]-Asum[y-1]
  
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]
 
for i in range(Q):
  print(ans[i])

Solution (Python):



import bisect

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

A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0

for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  





y=N//2-1
ans=[0]*Q
for x,i in X:
  while y<=N-1 and x>A[y]:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  
  ans[i]+=Asum[N-1]-Asum[y-1]
  
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])

Solution (Python):
n,q = map(int,input().split())
a = list(map(int,input().split()))
x = [int(input()) for _ in range (q)]

sort_x = sorted(x)
ans = {}
if n % 2 == 1:
    small_position = 0
    border_position = int((n-1)/2)
else:
    small_position = 1
    border_position = int(n/2)
sum_all = sum(a[border_position:])
a.append(1000000000)
a.append(1000000000)
x_index = 0
flag = False

for compare in a[border_position:]:
    compare_x = sort_x[x_index]
    small_a = a[small_position]
    while 2*sort_x[x_index] - small_a <= compare:
        ans[sort_x[x_index]] = sum_all
        x_index += 1
        if x_index == q:
            flag = True
            break
    sum_all = sum_all + small_a - compare
    small_position += 2
    if flag:
        break
for x_i in x:
    print(ans[x_i])

Solution (Python):

from bisect import bisect
N, Q = map(int, input().split())
A = [0] * (N % 2) + list(map(int, input().split()))

HF = len(A) // 2
li = []
cumsum = [sum(A[HF:])]

for i in range(HF - 1):
    left = A[2 * i + 1]
    right = A[i + HF]
    li += [(left + right) // 2 + 1]
    cumsum += [cumsum[-1] + left - right]

for _ in range(Q):
    X = int(input())
    print(cumsum[bisect(li, X)])

Solution (Python):
from itertools import accumulate
import sys


def check(X, k):
    
    L, R = As[N-2*k-1], As[N-k-1]
    return abs(L-X) > abs(X-R)

N, Q = map(int, input().split())
As = list(map(int, input().split()))
Xs = [(int(input()), iX) for iX in range(Q)]

if N == 2:
    print('\n'.join(map(str, [As[-1]]*Q)))
    sys.exit()

numT = (N+1) // 2  
Ascs = As[::2] if N % 2 else As[1::2]
Descs = As[::-1]
accAscs = [0] + list(accumulate(Ascs))
accDescs = [0] + list(accumulate(Descs))


scores = [0] * (numT+1)
for k in range(1, numT+1):
    scores[k] = accDescs[k] + accAscs[numT - k]


anss = [0] * Q
k = 1
for X, iX in sorted(Xs, reverse=True):
    
    while not check(X, k):
        k += 1
    anss[iX] = scores[k]

print('\n'.join(map(str, anss)))

Solution (Python):
def d_nearest_card_game(N, Q, A, X):
    
    
    
    
    
    
    
    

    
    

    
    
    
    
    

    
    
    import bisect

    a = A[::-1]  
    
    cumsum, evensum = [0] * (N + 1), [0] * (N + 1)
    for k, a_k in enumerate(a):
        cumsum[k + 1] = cumsum[k] + a_k
        evensum[k + 1] = evensum[k] + (a_k if k % 2 == 0 else 0)

    
    threshold, threshold_score = [], []
    for k in range((N - 1) // 2):
        threshold.append((a[k + 1] + a[2 * k + 2]) // 2 + 1)
        threshold_score.append((cumsum[k + 1] - cumsum[0]) + (evensum[N] - evensum[2 * k + 2]))

    
    threshold = threshold[::-1]
    threshold_score = threshold_score[::-1]

    ans = []
    for x in X:
        idx = bisect.bisect_right(threshold, x)
        if idx == 0:
            ans.append(cumsum[(N + 1) // 2] - cumsum[0])
        else:
            ans.append(threshold_score[idx - 1])
    ans = '\n'.join(map(str, ans))
    return ans

N, Q = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
X = [int(input()) for _ in range(Q)]
print(d_nearest_card_game(N, Q, A, X))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,q = li()
a = list(li())
x = [ni() for _ in range(q)]


cum_nor = list(accumulate(a))
cum_odd = list(accumulate(a[::2]))
cum_evn = list(accumulate(a[1::2]))
cum_kog = [cum_odd[i//2] if i%2==0 else cum_evn[i//2] for i in range(n)]


def check(a:list, tak:int, pivot:int):
    if tak > (len(a)+1)//2:
        return False
    
    if pivot-a[-2*tak+1] > a[-tak]-pivot:
        return False
    else:
        return True
        
    
def binsearch(a:list,xi:int):
    low = 1
    high = len(a)
    while high-low > 1:
        mid = (high+low) // 2
        if check(a,mid,xi):
            low = mid
        else:
            high = mid
            
    return low


for xi in x:
    tak = binsearch(a,xi)
    ans = cum_nor[-1] - cum_nor[-tak-1]
    if 2*tak < n:
        ans += cum_kog[-2*tak-1] 
    
    print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left
from itertools import accumulate

n,q = li()
a = list(li())
x = [ni() for _ in range(q)]


cum_nor = list(accumulate(a))
cum_odd = list(accumulate(a[::2]))
cum_evn = list(accumulate(a[1::2]))
cum_kog = [cum_odd[i//2] if i%2==0 else cum_evn[i//2] for i in range(n)]


def check(a:list, tak:int, pivot:int):
    if tak > (len(a)+1)//2:
        return False
    
    if pivot-a[-2*tak+1] > a[-tak]-pivot:
        return False
    else:
        return True
        
    
def binsearch(a:list,xi:int):
    low = 1
    high = len(a)
    while high-low > 1:
        mid = (high+low) // 2
        if check(a,mid,xi):
            low = mid
        else:
            high = mid
            
    return low


for xi in x:
    tak = binsearch(a,xi)
    ans = cum_nor[-1] - cum_nor[-tak-1]
    if 2*tak < n:
        ans += cum_kog[-2*tak-1] 
    
    print(ans)

Solution (Python):
import bisect

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

sumList=[]
sep2SumList=[]
for i in range(n):
    if i==0:
        sumList.append(aList[i])
    else:
        sumList.append(sumList[-1]+aList[i])
    if n%2==0:
        if i%2==1:
            if i==1:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])
    else:
        if i%2==0:
            if i==0:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])

                
sakaime=[]
anskazu=(n+1)//2
for i in range(anskazu):
    sakaime.append((aList[n-(i+1+1)]+aList[n-((i+1+1)*2-1)])//2)
sakaime.reverse()
sakaime=sakaime[1:]

def kotae(x):
    bisect.bisect_left(sakaime,x)
    num=len(sakaime)+1-bisect.bisect_left(sakaime,x)
    if num==len(sakaime)+1:
        ans=sumList[-1]-sumList[-1-num]
    else:
        ans=sumList[-1]-sumList[-1-num]+sep2SumList[(n-num*2+1)//2-1] 
    return ans

for i in range(q):
  x=int(input())
  print(kotae(x))

Solution (Python):
import bisect

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

sumList=[]
sep2SumList=[]
for i in range(n):
    if i==0:
        sumList.append(aList[i])
    else:
        sumList.append(sumList[-1]+aList[i])
    if n%2==0:
        if i%2==1:
            if i==1:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])
    else:
        if i%2==0:
            if i==0:
                sep2SumList.append(aList[i])
            else:
                sep2SumList.append(sep2SumList[-1]+aList[i])

                
sakaime=[]
anskazu=(n+1)//2
for i in range(anskazu):
    sakaime.append((aList[n-(i+1+1)]+aList[n-((i+1+1)*2-1)])//2)
sakaime.reverse()
sakaime=sakaime[1:]

def kotae(x):
    bisect.bisect_left(sakaime,x)
    num=len(sakaime)+1-bisect.bisect_left(sakaime,x)
    if num==len(sakaime)+1:
        ans=sumList[-1]-sumList[-1-num]
    else:
        ans=sumList[-1]-sumList[-1-num]+sep2SumList[(n-num*2+1)//2-1]
    return ans

for i in range(q):
  x=int(input())
  print(kotae(x))

Solution (Python):
import sys
input = sys.stdin.readline

import bisect

n, q = map(int, input().split())
a = list(map(int, input().split()))
X = []
for i in range(q):
    X.append((int(input()), i))
X.sort(key=lambda x: x[0])



acum = [0] * n
acum2 = [0] * n
a_cum = 0
a_cum2 = 0
for i in range(n):
    a_cum += a[i]
    acum[i] = a_cum
    if i - 2 >= 0:
        acum2[i] = acum2[i - 2] + a[i]
    else:
        acum2[i] = a[i]


ans = [0] * q



y = n//2 - 1
for x, i in X:
    
    while y <= n-1 and a[y] < x:
        y += 1
    while y <= n-1:
        upper = n - y  
        lower = y + 1 - bisect.bisect_left(a, 2*x - a[y])  
        
        
        
        if upper > lower:
            y += 1
        else:
            break

    
    ans[i] += acum[n-1] - acum[y-1]
    if 2 * y - n <= 0:
        continue
    ans[i] += acum2[2 * y - n - 1]

for i in range(q):
    print(ans[i])

Solution (Python):
n, q = map(int, input().split())
a = list(map(int, input().split()))
x = [int(input()) for _ in range(q)]
sort_x = sorted(x)
ans = {}
if n%2== 1:
    small_position = 0
    border_position = int((n-1)/2)
else:
    small_position = 1
    border_position = int(n/2)
sum_all = sum(a[border_position:])
a.append(10000000000)
a.append(10000000000)
x_index = 0
flag = False
for compare in a[border_position:]:
    compare_x = sort_x[x_index]
    small_a = a[small_position]
    while 2*sort_x[x_index] - small_a <= compare:
        ans[sort_x[x_index]] = sum_all
        x_index += 1
        if x_index == q:
            flag = True
            break
    sum_all = sum_all + small_a - compare
    small_position += 2
    if flag:
        break

for x_i in x:
    print(ans[x_i])

Solution (Python):
import itertools
import sys
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
def f(y):
    return abs(x-A[y])
N, Q = inpl()
A = inpl()
SA = list(itertools.accumulate(A))
if N%2 :
    B = [v for i, v in enumerate(A) if not i%2]
    B = [0] + list(itertools.accumulate(B))
else:
    B = [v for i, v in enumerate(A) if i%2]
    B = [0] + list(itertools.accumulate(B))
    
for _ in range(Q):
    x = int(input())
    lo = 1
    hi = -(-N//2) + 1
    while hi - lo >1:
        mid = (lo+hi)//2
        if mid == 1:
            continue
        if max(f(N-mid-1), f(N-2*mid+1)) <= f(N-mid):
            lo = mid
        else:
            hi = mid    
    print(SA[N-1] - SA[N-lo-1] + B[-((2*lo-N)//2)])

Solution (Python):
from bisect import bisect_left
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


N, Q = map(int, input().split())
A = [int(s) for s in input().split()]
X = []
for _ in range(Q):
    X.append(int(input()))


s = [0] * (N + 1)
for i in range(1, N + 1):
    s[i] = s[i - 1] + A[i - 1]
t = [0, A[0]] + [0] * (N - 1)
for i in range(2, N + 1):
    t[i] = t[i - 2] + A[i - 1]


def index_left(x, i):
    val = 2 * x - A[i]
    return bisect_left(A, val)


def nankaime(x, i):
    """requires x <= A[i]"""
    return i - index_left(x, i) + 1


def npi(x, i):
    return nankaime(x, i) + i


def index_right(x, istart):
    ls = LazySequence(lambda i: npi(x, i + istart), N - istart)
    return istart + bisect_left(ls, N) - 1


def getans(x):
    istart = bisect_left(A, x)
    if istart == N:
        return t[N]
    j = index_right(x, istart)
    turn = N - 1 - j
    i = j - turn + 1
    return s[N] - s[j + 1] + (t[i] if i > 0 else 0)


for i in range(Q):
    print(getans(X[i]))

Solution (Python):
from itertools import accumulate
import math
import bisect
n,q = map(int, input().split())
a = list(map(int, input().split()))

a_ac = [0] + list(accumulate(a))
taka_ac = [0] + list(accumulate(reversed(a[::-2]))) 
aoki_ac = [0] + list(accumulate(reversed(a[-2::-2]))) 
x = []
y = [10000000000]
z = [taka_ac[-1]]
for i in range(q):
  x.append(int(input()))
if n > 2:
  for i in range((n-1)//2):
    y.append((a[-i-2]+a[-i-3-i])//2)
    z.append(taka_ac[-i-3]+a_ac[-1]-a_ac[-i-3])
y.reverse()
z.reverse()
if n > 2:
  for i in x:
    print(z[bisect.bisect_left(y,i)])
else:
  for i in x:
    print(a[1])

Solution (Python):
import bisect

I = lambda:[int(i) for i in input().split()]
n, q = I()
A = [0] + I() if n % 2 else I()

m = len(A)//2
L = []
S = [sum(A[m:])]

for i in range(m-1):
  l = A[2 * i + 1]
  r = A[i + m]
  L+= [(l + r)//2]
  S+= [S[-1] + l - r]

for _ in range(q):
  print(S[bisect.bisect_left(L,int(input()))])

Solution (Python):
def emulate(A, x, cumsum, cumsum_skip):
    left = 0
    right = len(A)-2
    while left < right:
        i = (left + right) // 2
        j = len(A) - (len(A) - (i+1)) // 2 - 1
        if x - A[i] <= A[j] - x:
            right = i
        else:
            left = i + 1
    i = (left + right) // 2
    j = len(A) - (len(A) - (i+1)) // 2 - 1
    retval = 0
    if i >= 1:
        retval += cumsum_skip[i-1]
    retval += cumsum[len(A)-1] - cumsum[j-1]
    return retval


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    cumsum = [0] * N
    cumsum_skip = [0] * N
    cumsum[0] = A[0]
    cumsum_skip[0] = A[0] if N % 2 == 1 else 0
    for i in range(1, N):
        cumsum[i] = cumsum[i-1] + A[i]
        if (N - i) % 2 == 1:
            cumsum_skip[i] = cumsum_skip[i-1] + A[i]
        else:
            cumsum_skip[i] = cumsum_skip[i-1]
    for _ in range(Q):
        x = int(input())
        print(emulate(A, x, cumsum, cumsum_skip))


if __name__ == "__main__":
    main()

Solution (Python):
N, Q = map(int, input().split())
A = [int(x) for x in input().split()]
B = [a for a in A]
for i in range(N - 2, -1, -1):
  B[i] += B[i + 1]
C = [a for a in A]
for i in range(2, N):
  C[i] += C[i - 2]
D = [0 for i in range(N)]
for i in range(1, N + 1):
  if N - 1 - 2 * i < 0:
    break
  D[N - i] = (A[N - 1 - i] + A[N - 1 - 2 * i]) // 2 + 1
E = [b for b in B]
for i in range(1, N + 1):
  if N - 2 * i - 1 < 0:
    break
  E[N - i] += C[N - 2 * i - 1]
def binsearch(upper, lower, x):
  if x >= D[upper]:
    return upper
  if upper - lower == 1:
    return lower
  else:
    mid = (upper + lower) // 2
    if D[mid] <= x:
      return binsearch(upper, mid, x)
    else:
      return binsearch(mid, lower, x)
for q in range(Q):
  x = int(input())
  print(E[binsearch(N - 1, 0, x)])

Solution (Python):
from bisect import bisect_left
N,Q=map(int,input().split())
A=[int(i) for i in input().split()]
P=[]
m=N//2
for k in range(N-m-1):
  P.append((A[k+m]+A[2*(k+m)-N+1])/2)
S,S_o,S_e=[0],[0],[0]
for i in range(N):
  S.append(S[-1]+A[i])
  if i%2==0:
    S_o.append(S_o[-1]+A[i])
    S_e.append(S_e[-1])
  if i%2==1:
    S_o.append(S_o[-1])
    S_e.append(S_e[-1]+A[i])
for q in range(Q):
  a=int(input())
  l=bisect_left(P,a)
  if N%2:
    ans=S[N]-S[N-m+l-1]+S_o[max(N-2*(m-l+1),0)]
  else:
    ans=S[N]-S[N-m+l]+S_e[max(N-2*(m-l),0)]
  print(ans)

Solution (Python):
import sys
import bisect

input = sys.stdin.readline

N,Q=map(int,input().split())
A=list(map(int,input().split()))
X=[int(input()) for i in range(Q)]

XLIST=[]
for i in range(1,N//2+1):
    if i+1<=N and 2*i+1<=N:
        XLIST.append((A[-i-1]+A[-2*i-1])/2)



SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)

SUMODD=[0]
for i in range(N-1,-1,-2):
    SUMODD.append(SUMODD[-1]+A[i])

ANSLIST=[]
ANSLEN=(N+1)//2

for i in range(ANSLEN):
    ANS=0

    ANS+=SUM[-1]-SUM[-1-ANSLEN+i]

    ANS+=SUMODD[-1]-SUMODD[-1-i]

    ANSLIST.append(ANS)
    
XLIST.reverse()

for x in X:
    print(ANSLIST[bisect.bisect_left(XLIST,x)])

Solution (Python):



import bisect

n,q = [int(i) for i in input().split()]


a = [int(i) for i in input().split()]
if n%2 == 1:
    n+=1
    a.insert(0, 0)


sikiri = [(a[2*i+1] + a[i+n//2])//2 for i in range(n//2-1)]

s = sum(a[n//2:])
ans = [s]
for i in range(n//2-1):
    s = s - a[i+n//2] + a[2*i+1]
    ans.append(s)








for _ in range(q):
    x = int(input())
    i = bisect.bisect_left(sikiri,x)
    print(ans[i])

Solution (Python):
N, Q = map(int, input().split())
A = list(map(int, input().split()))
X = [int(input()) for i in range(Q)]
B = [0, sum(A[::-1][::2])]
W = [0, sum(A[::-1][::2])]

for i in range(1, (N+1)//2):
    d = (A[-i-1] - A[-i*2-1])
    B.append(B[-1] + d)
    W.append(W[-1] - d)

for q in X:
    l, r = 1, (N+1)//2

    while r-l>0:
        a = (r+l)//2+1
        b = A[-a]
        db = b-q
        w = A[-a*2+1]
        dw = q-w
        if dw <= db:
            l = a
        else:
            r = a-1

    print(B[r])

Solution (Python):
from math import ceil
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]
AltTake = [0 for a in range(N)]
GetAll = [0 for a in range(N)]
AltTake[0], AltTake[1] = A[0], A[1]
GetAll[-1] = A[-1]
BlockList = [0 for i in range(ceil(N/2))]
maxBlock = ceil(N/2)

for i in range(2, N):
    AltTake[i] = A[i] + AltTake[i-2]
for i in reversed(range(N-1)):
    GetAll[i] = GetAll[i+1] + A[i]
for i in range(ceil(N/2) - 1):
        BlockList[-i-1] = (A[-i-2] + A[-2*i - 3]) // 2 + 1

def BSearch(x, L):
    left, right = 0, len(L)
    while right - left > 1:
        mid = (right + left)//2
        if L[mid] > x:
            right = mid
        else:
            left = mid
    return left

for _ in range(Q):
    block = maxBlock - BSearch(int(input()), BlockList)
    if block == maxBlock: print(GetAll[-block])
    else: print(GetAll[-block] + AltTake[N - block * 2 -1])

Solution (Python):
N,Q=map(int,input().split())
A=[int(i) for i in input().split()]
X=[int(input()) for i in range(Q)]
if N%2==0:
    ta=N//2
    ao=N//2
else:
    ta=N//2+1
    ao=N//2
L=[0]*(N+1)
M0=[0]*(ta+1)
M1=[0]*(ao+1)
for i in range(N):
    L[i+1]=L[i]+A[i]
for i in range(ta):
    M0[i+1]=M0[i]+A[i*2]
for i in range(ao):
    M1[i+1]=M1[i]+A[i*2+1]

def shin(z):
    ma=N-1
    mi=0
    while ma-mi>1:
        mid=(ma+mi)//2
        if check(mid,z):
            ma=mid
        else:
            mi=mid
    


    nowta = ma
    get = N - 1 - ma + 1  
    ans = 0
    if get == ta:
        ans = L[N] - L[nowta]
    else:
        ans = L[N] - L[nowta]
        nowao = nowta - get - 1
        if nowao % 2 == 1:
            ans += M1[nowao // 2 + 1]

        else:
            ans += M0[nowao // 2 + 1]
    print(ans)

def check(x,z):
    p=(N-1)-x+1
    
    if x-p+1<0:
        return False
    if abs(z-A[x-p+1])<=abs(z-A[x]):
        return True
    else:
        return False
for x in X:
    shin(x)

Solution (Python):

N, Q = map(int, input().split())
A_list = list(map(int, input().split()))
q_list = [0]*Q
for i in range(Q):
    q_list[i] = int(input())




M = (N+1)//2
S1 = [0]*M
S2 = [0]*M

s1 = 0
s2 = 0
for i in range(M):
    s1 += A_list[N-1-i]
    S1[i] = s1
    s2 += A_list[N-1-2*i]
    S2[i] = s2


bins = [0]*(M-1)
for i in range(M-1):
    bins[i] = (A_list[N - (i+2)] + A_list[N - (2*i+3)]) / 2


def bisearch(q):
    
    if q > bins[0]:
        return 0
    elif q <= bins[M-2]:
        return M - 1
    
    l = 0
    r = M - 2
    while l < r - 1:
        m = (l + r) // 2
        if q > bins[m]:
            r = m
        else:
            l = m
    return l+1
    
    
if N > 2:
    
    for q in q_list:
        r = bisearch(q)
        print(S1[r]+s2-S2[r])
else:
    for q in q_list:
        print(A_list[1])

Solution (Python):
import sys
import bisect

input = sys.stdin.readline

N,Q=map(int,input().split())
A=list(map(int,input().split()))
X=[int(input()) for i in range(Q)]

XLIST=[]
for i in range(1,N//2+1):
    if i+1<=N and 2*i+1<=N:
        XLIST.append((A[-i-1]+A[-2*i-1])/2)



SUM=[0]
for a in A:
    SUM.append(SUM[-1]+a)

SUMODD=[0]
for i in range(N-1,-1,-2):
    SUMODD.append(SUMODD[-1]+A[i])

ANSLIST=[]
ANSLEN=(N+1)//2

for i in range(ANSLEN):
    ANS=0

    ANS+=SUM[-1]-SUM[-1-ANSLEN+i]

    ANS+=SUMODD[-1]-SUMODD[-1-i]

    ANSLIST.append(ANS)
    
XLIST.reverse()

for x in X:
    print(ANSLIST[bisect.bisect_left(XLIST,x)])

Solution (Python):
import sys

n, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
xxx = sorted(((int(line), i) for i, line in enumerate(sys.stdin.readlines())), reverse=True)
total = sum(aaa)
tmp = sum(aaa[n // 2:])
ans = [sum(aaa[-1::-2])] * q
if n % 2 == 0:
    l, r = 1, n // 2
else:
    l, r = 0, n // 2
while l < r:
    al, ar = aaa[l], aaa[r]
    m = (al + ar) // 2
    while xxx and xxx[-1][0] <= m:
        x, i = xxx.pop()
        ans[i] = tmp
    if not xxx:
        break
    tmp += al - ar
    l += 2
    r += 1
print('\n'.join(map(str, ans)))