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):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, q = LI()
    a = LI()
    odd = [0] * n
    even = [0] * n
    def f(mid):
        return abs(a[mid] - x) < abs(a[mid - (n - mid - 1)] - x)
    for i in range(n):
        if i & 1:
            odd[i] += odd[i - 1] + a[i]
        else:
            odd[i] += odd[i - 1]
    acc = list(itertools.accumulate(a))
    for _ in range(q):
        x = II()
        ok = 0
        ng = n
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            if f(mid):
                ok = mid
            else:
                ng = mid
        ok = ng - (n - ng)
        ng -= 1
        ans = acc[-1] - acc[ng]
        if ok < 0:
            pass
        elif n & 1:
            ans += acc[ok]-odd[ok]
        else:
            ans += odd[ok]
        print(ans)
        
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
def calc(x):
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    return l
    
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
B = [A[0]] + [0] * (N-1)
for i in range(1, N):
    B[i] = B[i-1] + A[i]
C = [A[0]] + [0] * (N-1)
for i in range(2, N, 2):
    C[i] = C[i-2] + A[i]
C[-1] += C[-2]
for _ in range(Q):
    x = int(input())
    c = calc(x)
    print(B[c] + (C[-1] - C[2*c] if c*2<=N else 0))

Solution (Python):
from bisect import bisect_left, bisect_right

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

A.reverse()

evenA = [0] * (N + 1)
accA = [0] * (N + 1)

for i in range(1, N + 1):
    evenA[i] = evenA[i - 1] + (A[i - 1] if i % 2 == 1 else 0)
    accA[i] = accA[i - 1] + A[i - 1]

borders = []
scores = []

for i in range(1, N // 2 + N % 2):
    border = (A[i] + A[i * 2]) // 2 + 1
    borders.append(border)

    score = accA[i] + (evenA[N] - evenA[i * 2])
    scores.append(score)

scores.append(accA[N // 2 + N % 2])

borders.reverse()
scores.reverse()

for x in X:
    i = bisect_right(borders, x)
    print(scores[i])

Solution (Python):
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=min(nn,n-1)

    for i,ini in ix:
        while check(k)==True:k-=1
        k+=1
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()

Solution (Python):
def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

    for i,ini in ix:
        l=1
        u=k
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()

Solution (Python):
from itertools import accumulate,chain
def bisect(ng, ok, judge):
    while abs(ng-ok) > 1:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

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

if N % 2 == 1:
    A = list(chain((0,),map(int,input().split())))
    N += 1
else:
    A = list(map(int,input().split()))

X = [int(input()) for _ in range(Q)]

oacc = list(chain((0,),accumulate(A[1::2])))
acc = list(chain((0,),accumulate(A)))

check = lambda x: lambda i: x*2 < A[-i]+A[-2*i]
M = N//2
for x in X:
    c = check(x)
    if c(M):
        print(acc[-1]-acc[M])
    elif not c(1):
        print(oacc[-1])
    else:
        i = bisect(M, 1, c)
        if x*2 <= A[-i-1] + A[-2*i-1]:
            i += 1
        s = acc[N]-acc[-i-1]
        if 2*i < N:
            s += oacc[(N-2*i)//2]
        print(s)

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

a = sorted(a)
ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]
    
ruiseki2 = [0]*(n+1)
if n % 2 == 1:
    for i in range(n):
        if i % 2 == 0:
            ruiseki2[i+1] = ruiseki2[i] + a[i]
        else:
            ruiseki2[i+1] = ruiseki2[i]

if n % 2 == 0:
    for i in range(n):
        if i % 2 == 1:
            ruiseki2[i+1] = ruiseki2[i] + a[i]
        else:
            ruiseki2[i+1] = ruiseki2[i]

def solve(mid, num):
    r = -((-mid) // 2)
    l = mid
    r_pos = n - r
    l_pos = n - l
    if abs(a[l_pos] - num) <= abs(a[r_pos] - num):
        return True
    else:
        return False

for i in range(q):
    num = query[i]
    ok = 1
    ng = n + 1 
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid, num):
            ok = mid
        else:
            ng = mid
    ans = 0
    ans += ruiseki[n] - ruiseki[n-(ok+1)//2]
    nokori = n - ok
    ans += ruiseki2[nokori]
    print(ans)

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

N, Q = map(int, input().split())
A = list(map(int, input().split()))
Query = [int(input()) for _ in range(Q)]
INF = 10**14

E = [0]
O = [0]
e = 0
o = 0
for i, a in enumerate(A):
    if i % 2 == 0:
        e += a
    else:
        o += a
    E.append(e)
    O.append(o)

S = [0]
s = 0
for a in reversed(A):
    s += a
    S.append(s)

for X in Query:
    ind = N
    if X > A[-1]:
        l = 0
    else:
        l = 0
        r = N+1
        while r-l > 1:
            m = (r+l)//2
            in_left = A[-m]
            in_right = A[-m+m//2-1]
            out_left = A[-m-1] if m < N else -INF
            out_right = A[-m+m//2] if m > 0 else INF
            if X <= out_left:
                l = m
            elif out_right <= X:
                r = m
            else:
                if abs(X-out_left) <= abs(in_right-X):
                    l = m
                elif abs(X-in_left) > abs(out_right - X):
                    r = m
                else:
                    l = m
                    break
    
    ans = S[l-l//2]
    if l%2 != (N-l)%2:
        ans += E[N-l]
    else:
        ans += O[N-l]
    
    print(ans)

Solution (Python):
from bisect import bisect_left

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

i = (N & 1) ^ 1
j = N // 2

st = sum(A[j:])

ret_k = []
ret_v = []

while i < j :
    ret_k.append((A[i] + A[j]) // 2)
    ret_v.append(st)
    st = st - A[j] + A[i]
    i += 2
    j += 1
ret_k.append(1e+12)
ret_v.append(st)

for x in X :
    print(ret_v[bisect_left(ret_k, x)])

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,Q = II()
A = III()
X = Line(Q,1)

if N==2:
    for _ in range(Q):
        print(A[-1])
    exit()

sum_list = [0]*N
now_odd = 0
now_even = 0
for i in range(N):
    if i%2==0:
        now_even += A[i]
        sum_list[i] = now_even
    else:
        now_odd += A[i]
        sum_list[i] = now_odd        

left_sum = [0]*N
now = 0
for i in range(N)[::-1]:
    now += A[i]
    left_sum[i] = now

for x in X:
    left = 0
    right = N//2
    while (right-left>1):
        mid = left + (right-left)//2
        if abs(A[N-mid-2]-x)<abs(A[N-2*mid-2]-x):
            right = mid
        else:
            left = mid
    right1 = right

    left = 0
    right = N//2 + 1
    while (right-left>1):
        mid = left + (right-left)//2
        if abs(A[N-mid-1]-x)<abs(A[N-2*mid-1]-x):
            right = mid
        else:
            left = mid
    right2 = right

    flag = False
    if right1 != right2:
        flag = True

    ans = left_sum[N-right2]

    if flag:
        if N-right1-right2-2>=0:
            ans += sum_list[N-right1-right2-2]
    else:
        if N-right1-right2-1>=0:
            ans += sum_list[N-right1-right2-1]
    print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Q = map(int,readline().split())
A = np.array(readline().split(),np.int64)
X = np.array(read().split(),np.int64)

INF=10**15
A = np.concatenate([[-INF,-INF,-INF,-INF],A])

"""
・ある数が後手の右端となるのはどのような場合か
・n番目の右側にr>=1個あるとする
・【長さが奇数のときは、先頭に0を追加しておく】
  → 後手は、[n-r+1,n]をとって、先手は[n+1:]およびn-rを回収する。
・n+1番目をとらない iff r-1個自由にとると n+1番目を含まない iff |A_{n+1}-x| >= |A_{n-r+2}-x|
  iff r = 1 or x <= (A_{n+1}+A_{n-r+2})/2 iff r = 1 or x <= (A_{n+1}+A_{n-r+2})//2
・n-r番目をとらない iff r個自由にとると、n-r番目を含まない iff |A_n-x| < |A_{n-r}-x|
  iff x > (A_n+A_{n-r})/2 iff x > (A_n+A_{n-r})//2
"""

n = np.arange(N+4)
r = N-n+3
ind = (n-r>=0)&(r>=1); n = n[ind]; r = r[ind]

lower = (A[n] + A[n-r])//2 + 1




Acum = np.cumsum(A)
Acum_ev = np.zeros_like(A)
Acum_ev[::2] = A[::2].cumsum()
Acum_ev[1::2] = A[1::2].cumsum()
score = Acum[-1] - Acum[n] + Acum_ev[n-r] + INF + INF

I = np.searchsorted(lower,X,side='right') - 1
answer = score[I]

print('\n'.join(answer.astype(str)))

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

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

for q in range(Q):
	x = int(input())
	if x >= A[-1]:
		print(even_odd_sum[-1])
	else:
		loc_min = bisect.bisect_left(A, x)
		loc_min = max(loc_min, N // 2)
		loc_max = (loc_min + N) // 2

		t = (loc_min + loc_max) // 2


		
		while (loc_min <= loc_max):

			if 2*t - N - 1 >= 0 and A[t - 1] - x >= x - A[2*t - N - 1]:
				loc_max = t - 1
			elif 2*t - N >= 0 and A[t] - x < x - A[2*t - N]:
				loc_min = t + 1
			elif 2*t - N < 0 and A[t] - x < x - A[0]:
				loc_min = t + 1
			else:
				break

			t = (loc_min + loc_max) // 2
		ans = sum_list[-1] - sum_list[t] + even_odd_sum[2*t - N - 1 + 2]
		print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

from bisect import bisect_left

n, q = map(int, input().split())
a = list(map(int, input().split()))
xs = [int(input()) for i in range(q)]

s = [0]*(n+1)
se = [0]*(n+1)
for i in range(n):
    s[i+1] = s[i] + a[i]
    if i :
        se[i+1] = se[i-1]
    se[i+1] += a[i]

def check(x, k):
    if k > n:
        return False

    Tk = (k+1)//2
    i = bisect_left(a, x- (a[n-Tk]-x))
    return i+k <= n

for x in xs:
    left = 0
    right = n+1
    while right-left > 1:
        mid = (left+right)//2
        if check(x, mid):
            left = mid
        else:
            right = mid
    top = (left+1)//2
    ans = 0
    ans += s[n] - s[n-top]
    if left%2:
        left += 1
    ans += se[n-left] if n-left>=0 else 0
    print(ans)

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

INF = 10**12
n, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]


sum_even = [0] * (n + 1)
sum_odd = [0] * (n + 1)
sum_all = [0] * (n + 1)
for i, item in enumerate(a):
    if i % 2 == 0:
        sum_odd[i+1] = sum_odd[i] + a[i]
        sum_even[i+1] = sum_even[i]
    else:
        sum_even[i+1] = sum_even[i] + a[i]
        sum_odd[i+1] = sum_odd[i]
    sum_all[i+1] = sum_all[i] + a[i]


a.append(INF)
ans = []
for i in range(q):
    x = int(input())
    
    
    l = 0; r = n - 1
    while r - l > 1:
        m = (r + l) // 2
        rng = abs(x - a[m])
        t_num = n - m
        a_num = n - t_num - (bisect.bisect_left(a, x - rng))
        if t_num <= a_num + 1:
            r = m
        else:
            l = m
    rng = abs(x - a[r])
    t_num = n - r
    rest = n - 2 * t_num
    t_sum = sum_all[n] - sum_all[n - t_num]
    a_sum = sum_all[r] - sum_all[r - t_num]

    
    if n - t_num * 2 > 0:
        if rest % 2 == 0:
            t_sum += sum_even[rest]
            a_sum += sum_odd[rest]
        else:
            t_sum += sum_odd[rest]
            a_sum += sum_even[rest]
    ans.append(t_sum)

print("\n".join([str(item) for item in ans]))

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

INF = 10**12
n, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]


sum_even = [0] * (n + 1)
sum_odd = [0] * (n + 1)
sum_all = [0] * (n + 1)
for i, item in enumerate(a):
    if i % 2 == 0:
        sum_odd[i+1] = sum_odd[i] + a[i]
        sum_even[i+1] = sum_even[i]
    else:
        sum_even[i+1] = sum_even[i] + a[i]
        sum_odd[i+1] = sum_odd[i]
    sum_all[i+1] = sum_all[i] + a[i]


a.append(INF)
ans = []
for i in range(q):
    
    x = int(input())
    l = 0
    r = n - 1
    
    while r - l > 1:
        m = (r + l) // 2
        rng = abs(x - a[m])
        t_num = n - m
        a_num = n - t_num - (bisect.bisect_left(a, x - rng))
        if t_num <= a_num + 1:
            r = m
        else:
            l = m
    rng = abs(x - a[r])
    t_num = n - r
    rest = n - 2 * t_num
    t_sum = sum_all[n] - sum_all[n - t_num]
    a_sum = sum_all[r] - sum_all[r - t_num]

    
    if n - t_num * 2 > 0:
        if rest % 2 == 0:
            t_sum += sum_even[rest]
            a_sum += sum_odd[rest]
        else:
            t_sum += sum_odd[rest]
            a_sum += sum_even[rest]
    ans.append(t_sum)

print("\n".join([str(item) for item in ans]))

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

INF = 10**12
n, q = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]


sum_even = [0] * (n + 1)
sum_odd = [0] * (n + 1)
sum_all = [0] * (n + 1)
for i, item in enumerate(a):
    if i % 2 == 0:
        sum_odd[i+1] = sum_odd[i] + a[i]
        sum_even[i+1] = sum_even[i]
    else:
        sum_even[i+1] = sum_even[i] + a[i]
        sum_odd[i+1] = sum_odd[i]
    sum_all[i+1] = sum_all[i] + a[i]


a.append(INF)
ans = []
for i in range(q):
    
    x = int(input())
    big = bisect.bisect_left(a, x)
    small = big - 1
    if (x - a[small]) ** 2 <= (x - a[big]) ** 2:
        l = small
    else:
        l = big
    r = n - 1
    while r - l > 1:
        m = (r + l) // 2
        rng = abs(x - a[m])
        taka = n - m
        aoki = n - taka - (bisect.bisect_left(a, x - rng))
        if taka <= aoki + 1:
            r = m
        else:
            l = m
    rng = abs(x - a[r])
    taka = n - r
    aoki = n - taka - (bisect.bisect_left(a, x - rng))
    taka_sum = sum_all[n] - sum_all[n - taka]
    aoki_sum = sum_all[r] - sum_all[r - taka]
    rest = n - taka * 2
    if rest > 0:
        if rest % 2 == 0:
            taka_sum += sum_even[rest]
            aoki_sum += sum_odd[rest]
        else:
            taka_sum += sum_odd[rest]
            aoki_sum += sum_even[rest]

    ans.append(taka_sum)
print("\n".join([str(item) for item in ans]))

Solution (Python):
from itertools import accumulate
from bisect import bisect

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



INF = 10**20
B = A[::-1]
Y = [(B[i] + B[2 * i]) // 2 + 1 for i in range(1, (N + 1) // 2)][::-1]
acc1 = list(accumulate(B))
acc2 = list(accumulate(B[2::2][::-1]))[::-1] + [0] * (N - (N - 1) // 2)
ans = '\n'.join(
    str(acc1[i] + acc2[i])
    for i in (
        len(Y) - bisect(Y, x)
        for x in X
    )
)

print(ans)

Solution (Python):
from bisect import bisect
n,q = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a,x,y,z = a[::-1],[0],[0],[]
for i in range(n):
    x.append(x[-1]+a[i])
    if 1-i%2: y.append(y[-1]+a[i])
    else: y.append(y[-1])
for i in range((n+1)//2): z.append(-1.0*(a[i]+a[2*i])/2)
for i in range(q):
    p = -int(input())
    m = bisect(z,p)
    if m==len(z): print(x[(n+1)//2])
    else: print(x[m]+y[n]-y[2*m])

Solution (Python):
import bisect
N,Q=map(int,input().split())
A=list(map(int,input().split()))
odd=[A[1]]
even=[A[0]]
Sum=[A[0],A[0]+A[1]]
for i in range(2,N):
    Sum.append(Sum[-1]+A[i])
    if i%2==0:
        even.append(even[-1]+A[i])
    elif i%2==1:
        odd.append(odd[-1]+A[i])
change=[]
data=[(0,N//2-1)]
R=N//2-1
L=0
for R in range(N//2,N-1):
    L=2*(R+1)-N
    change.append((A[L-1]+A[R])//2)
    data.append((L,R))
if N%2==1:
    Taka=even
    Aoki=odd
elif N%2==0:
    Taka=odd
    Aoki=even
for q in range(Q):
    x=int(input())
    idx=bisect.bisect_left(change,x)
    Range=data[idx]
    if Range[0]==0:
        print(Sum[-1]-Sum[Range[1]])
    else:
        print(Taka[(Range[0]-1)//2]+Sum[-1]-Sum[Range[1]])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,h,w = IR(3)
    print((n-h+1)*(n-w+1))
    return


def B():
    n = I()
    a,b = LI()
    p = LI()
    k = [0 for i in range(a+1)]
    k += [1 for i in range(b-a)]
    k += [2 for i in range(max(p)+1-b)]
    d = defaultdict(int)
    for i in p:
        d[k[i]] += 1
    ans = min(d[0],d[1],d[2])
    print(ans)
    return


def C():
    h,w = LI()
    s = SR(h)
    bfs_map = [[-1 for i in range(w)] for j in range(h)]
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "
                if bfs_map[y][x] < 0:
                    bfs_map[y][x] = 0
                    a = 1
                    b = 0
                    q = deque()
                    q.append([y,x])
                    while q:
                        n,m = q.popleft()
                        for dy,dx in d:
                            n2 = n+dy
                            m2 = m+dx
                            if 0 <= n2 < h and 0 <= m2 < w:
                                if s[n][m] != s[n2][m2] and bfs_map[n2][m2] < 0:
                                    if s[n2][m2] == "
                                    else:b += 1
                                    bfs_map[n2][m2] = 0
                                    q.append([n2,m2])
                    ans += a*b
    print(ans)
    return


def D():
    n,q = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    c = [a[i] if i%2 else 0 for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
        c[i+1] += c[i]
    for i in range(q):
        x = I()
        l = 0
        r = n
        while r-l > 1:
            m = (l+r)//2
            if abs(a[m]-x) < abs(a[m-(n-m-1)]-x):
                l = m
            else:
                r = m
        l = r-(n-r)
        r -= 1
        ans = b[n-1]-b[r]
        l -= 1
        if l >= 0:
            if not n%2:
                ans += c[l]
            else:
                ans += b[l]-c[l]
        print(ans)
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

Solution (Python):
n, q = map(int, input().split())
a = list(map(int, input().split()))
s = [0] 

for p in a:
	s.append(s[-1] + p)
oe = [a[0], a[1]]

for i in range(2, n):
	oe.append(oe[-2]+a[i])

for _ in range(q):
	x = int(input())
	if 2*x > a[n-2] + a[n-1]:
		print(oe[n-1])
	elif abs(x - a[0]) <= abs(x - a[n//2]):
		print(s[n] - s[n//2])
	else:
		ok = 0
		ng = n + 1
		while abs(ng-ok) > 1:
			mi = (ng+ok) // 2
			if abs(x - a[n - mi]) <= abs(x - a[n - (mi+1)//2]):
				ok = mi
			else:
				ng = mi
		ans = s[n] - s[n-(ok+1)//2]
		if n - (ok+1)//2 * 2 - 1 >= 0:
			ans += oe[n - (ok+1)//2 * 2 - 1]
		print(ans)

Solution (Python):
import bisect
def inpl(): return list(map(int,input().split()))

N, Q = inpl()
A = sorted(inpl(), key=lambda x: -x)
if N % 2:
    N += 1
    A.append(0)

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

biavg = [ -(A[i]+A[i*2])/2 for i in range(1,N//2) ]

def nsg(X):
    m = bisect.bisect_left(biavg, -X)
    if m < N//2-1 and biavg[m] == -X:
        m += 1

    return cumsum[m] + frogsum[N-2] - frogsum[m*2]


for _ in range(Q):
    X = int(input())
    print(nsg(X))

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(A, Q):
    N = len(A)
    A = A[::-1]

    s, es = [0] * (N + 1), [0] * (N + 1)
    for i in range(N):
        s[i + 1] = s[i] + A[i]
        es[i + 1] = es[i] + (A[i] if i % 2 == 0 else 0)

    x_list, sum_t_list = [], []
    for n in range((N - 1) // 2):
        x = (A[n + 1] + A[n * 2 + 2]) // 2 + 1
        sum_t = s[n + 1] + (es[N] - es[n * 2 + 2])
        x_list.append(x)
        sum_t_list.append(sum_t)

    x_list = x_list[::-1]
    sum_t_list = sum_t_list[::-1]

    for _ in range(Q):
        x = int(input())
        p = bisect_right(x_list, x)
        if p == 0:
            print(s[(N + 1) // 2])
        else:
            print(sum_t_list[p - 1])


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

    solve(A, Q)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve(A, Q):
    N = len(A)
    A = A[::-1]

    s, es = [0] * (N + 1), [0] * (N + 1)
    for i in range(N):
        s[i + 1] = s[i] + A[i]
        es[i + 1] = es[i] + (A[i] if i % 2 == 0 else 0)

    ths, vals = [], []
    for i in range((N - 1) // 2):
        th = (A[i + 1] + A[i * 2 + 2]) // 2 + 1
        val = (s[i + 1] - s[0]) + (es[N] - es[i * 2 + 2])
        ths.append(th)
        vals.append(val)

    ths = ths[::-1]
    vals = vals[::-1]

    for _ in range(Q):
        x = int(input())
        p = bisect_right(ths, x)
        if p == 0:
            print(s[(N + 1) // 2] - s[0])
        else:
            print(vals[p - 1])


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

    solve(A, Q)


if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 14

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

ALT = [0] * N
if N % 2:
    ALT[0] = A[0]
    for i in range(2, N, 2):
        ALT[i - 1] = ALT[i - 2]
        ALT[i] = ALT[i - 2] + A[i]
else:
    ALT[1] = A[1]
    for i in range(3, N, 2):
        ALT[i - 1] = ALT[i - 2]
        ALT[i] = ALT[i - 2] + A[i]

ALT = [0] + ALT

S = [0] * N + [0]
for i in range(N):
    S[i + 1] = S[i] + A[i]

A = [-INF] + A + [INF]
pos1 = pos2 = 0
x, index = X[0]
for i in range(N + 2):
    if x <= A[i]:
        if A[i] - x < x - A[i - 1]:
            pos1 = pos2 = i
        else:
            pos1 = pos2 = i - 1
        break

ans = [0] * Q
for x, index in X:
    while True:
        cnt1 = pos2 - pos1
        cnt2 = N - pos2 + 1
        if cnt2 - cnt1 >= 2:
            if A[pos2] - x < x - A[pos1 - 1]:
                pos2 += 1
            else:
                pos1 -= 1
        elif cnt1 > cnt2:
            if A[pos2 - 1] - x < x - A[pos1]:
                pos1 += 1
            else:
                pos2 -= 1
        elif A[pos2] - x < x - A[pos1]:
            pos1 += 1
            pos2 += 1
        elif A[pos2 - 1] - x >= x - A[pos1 - 1]:
            pos1 -= 1
            pos2 -= 1
        else:
            break
    ans[index] = S[N] - S[pos2 - 1] + ALT[pos1 - 1]

for a in ans:
    print a

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
A = LIST()

sm = sum([A[i] for i in range(N-1, -1, -2)])
borders = [(INF, sm)]
j = N-3
for i in range(N-2, N//2-1, -1):
    border =  (A[j] + A[i]) // 2
    val = A[i] - A[j]
    sm += val
    borders.append((border, sm))
    j -= 2
borders.sort()

for _ in range(Q):
    x = INT()
    idx = bisect_left(borders, (x, 0))
    print(borders[idx][1])

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

if n % 2:
    n += 1
    a.insert(0, 0)

border = [(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 += -a[i+n//2] + a[2*i+1]
    ans.append(s)

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