Given an array of integers, you must answer a number of queries. Each query consists of a single integer, $\boldsymbol{x}$, and is performed as follows:

Add $\boldsymbol{x}$ to each element of the array, permanently modifying it for any future queries.
Find the absolute value of each element in the array and print the sum of the absolute values on a new line.

Tip: The Input/Output for this challenge is very large, so you'll have to be creative in your approach to pass all test cases.

Function Description  

Complete the playingWithNumbers function in the editor below.  It should return an array of integers that represent the responses to each query.  

playingWithNumbers has the following parameter(s):  

arr: an array of integers  
queries: an array of integers  

Input Format

The first line contains an integer $n$ the number of elements in $\textbf{arr}$. 

The second line contains $n$ space-separated integers $arr\left[i\right]$. 

The third line contains an integer $\textit{q}$, the number of queries. 

The fourth line contains $\textit{q}$ space-separated integers $\boldsymbol{x}$ where $qumeries[j]=x$.    

Constraints

$1\leq n\leq5\times10^5$  
$1\leq q\leq5\times10^5$  
$-2000\leq arr[i]\leq2000$, where $0\leq i<n$.
$-2000\leq\textit{queries}[j]\leq2000$, where $0\leq j<q$

Output Format

For each query, print the sum of the absolute values of all the array's elements on a new line.

Sample Input
3
-1 2 -3
3
1 -2 3 

Sample Output
5
7
6

Explanation

Query 0: $x=1$ 

Array: $[-1,2,-3]\rightarrow[0,3,-2]$ 

The sum of the absolute values of the updated array's elements is $|0|+|3|+|-2|=0+3+2=5$.    

Query 1: $x=-2$ 

Array: $[0,3,-2]\rightarrow[-2,1,-4]$ 

The sum of the absolute values of the updated array's elements is $|-2|+|1|+|-4|=2+1+4=7$.   

Query 2: $x=3$ 

Array: $[-2,1,-4]\rightarrow[1,4,-1]$ 

The sum of the absolute values of the updated array's elements is $|1|+|4|+|-1|=1+4+1=6$.

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
from collections import Counter

def q(arr, queries):
	positive_n = [el for el in arr if el >= 0]
	negative_n = [el for el in arr if el < 0]
	pos_size = len(positive_n)
	neg_size = len(negative_n)
	positive = list(reversed(sorted(Counter(positive_n).items())))
	negative = sorted(Counter(negative_n).items())
	tot = sum((abs(el) for el in arr))
	diff = 0
	for q in queries:
		diff += q
		tot += pos_size * q - neg_size * q
		if q > 0:
			while neg_size and negative[-1][0] + diff >= 0:
				(n, count) = negative.pop()
				positive.append((n, count))
				pos_size += count
				neg_size -= count
				tot += abs(n + diff) * 2 * count
		else:
			while pos_size and positive[-1][0] + diff < 0:
				(n, count) = positive.pop()
				negative.append((n, count))
				neg_size += count
				pos_size -= count
				tot += abs(n + diff) * 2 * count
		yield tot
input()
arr = [int(s) for s in input().split()]
input()
que = [int(s) for s in input().split()]
for res in q(arr, que):
	print(res)


class RangeTree:

	def __init__(self, rl, rh, nums):
		self.rl = rl
		self.rh = rh
		if rh <= rl:
			self.num_sum = 0
		elif rh - rl == 1:
			self.num_sum = nums[rl]
		else:
			mid = (rl + rh) // 2
			self.left_child = RangeTree(rl, mid, nums)
			self.right_child = RangeTree(mid, rh, nums)
			self.num_sum = self.left_child.num_sum + self.right_child.num_sum

	def query_range(self, l, h):
		if self.rh <= self.rl or h <= self.rl or l >= self.rh:
			result = 0
		elif l <= self.rl < self.rh <= h:
			result = self.num_sum
		else:
			l = max(l, self.rl)
			h = min(h, self.rh)
			mid = (l + h) // 2
			result = self.left_child.query_range(l, h) + self.right_child.query_range(l, h)
		return result

class Maintainer:

	def __init__(self, nums):
		self.nums = sorted(nums)
		self.cur_added_sum = 0
		self.cur_sum = 0
		self.rt = RangeTree(0, len(self.nums), self.nums)
		self.least_larger = self.__least_larger()
		self.largest_less = self.__largest_less()
		self.cur_sum = sum([abs(x) for x in self.nums])

	def __least_larger(self):
		target = -self.cur_added_sum
		if target < self.nums[0]:
			return 0
		if target > self.nums[-1]:
			return len(self.nums)
		(head, tail) = (0, len(self.nums) - 1)
		while head < tail - 1:
			mid = (head + tail) // 2
			if self.nums[mid] <= target:
				head = mid
			elif self.nums[mid] > target:
				tail = mid
		if self.nums[tail] == target:
			return len(self.nums)
		else:
			return tail

	def __largest_less(self):
		target = -self.cur_added_sum
		if target > self.nums[-1]:
			return len(self.nums) - 1
		if target < self.nums[0]:
			return -1
		(head, tail) = (0, len(self.nums) - 1)
		while head < tail - 1:
			mid = (head + tail) // 2
			if self.nums[mid] < target:
				head = mid
			if self.nums[mid] >= target:
				tail = mid
		if self.nums[head] == target:
			return -1
		else:
			return head

	def query(self, x):
		if x == 0:
			return self.cur_sum
		self.cur_added_sum += x
		new_least_larger = self.__least_larger()
		new_largest_less = self.__largest_less()
		if x > 0:
			self.cur_sum += x * (len(self.nums) - self.largest_less - 1)
			self.cur_sum -= x * (new_largest_less + 1)
			after_change = self.rt.query_range(new_largest_less + 1, self.largest_less + 1) + self.cur_added_sum * (self.largest_less - new_largest_less)
			self.cur_sum += abs(after_change) - abs(after_change - x * (self.largest_less - new_largest_less))
		else:
			x = -x
			self.cur_sum += x * self.least_larger
			self.cur_sum -= x * (len(self.nums) - new_least_larger)
			after_change = self.rt.query_range(self.least_larger, new_least_larger) + self.cur_added_sum * (new_least_larger - self.least_larger)
			self.cur_sum += abs(after_change) - abs(after_change + x * (new_least_larger - self.least_larger))
		self.least_larger = new_least_larger
		self.largest_less = new_largest_less
		return self.cur_sum
N = int(input())
maintainer = Maintainer([int(x) for x in input().split()])
Q = int(input())
for x in [int(x) for x in input().split()]:
	print(maintainer.query(x))


from bisect import bisect_left, bisect_right
from itertools import accumulate
from io import StringIO

def query(q):
	if q == 0:
		return 0
	elif q > 0:
		s = bisect_left(ar, -q + 1)
		t = bisect_left(ar, 0)
		return (N - t - s) * q + 2 * (ra[t] - ra[s]) + q * (t - s)
	else:
		t = bisect_right(ar, -q - 1)
		s = bisect_right(ar, 0)
		return (N - t - s) * q - 2 * (ra[t] - ra[s]) - q * (t - s)
N = int(input())
ar = sorted((int(x) for x in input().split()))
ra = list(accumulate(ar))
ra.insert(0, 0)
absum = sum(map(abs, ar))
Q = int(input())
qq = 0
with StringIO() as sio:
	for qu in (int(x) for x in input().split()):
		qq += qu
		print(query(qq) + absum, file=sio)
	print(sio.getvalue())


from collections import Counter

def q(arr, queries):
	positive_n = [el for el in arr if el >= 0]
	negative_n = [el for el in arr if el < 0]
	pos_size = len(positive_n)
	neg_size = len(negative_n)
	positive = list(reversed(sorted(Counter(positive_n).items())))
	negative = sorted(Counter(negative_n).items())
	tot = sum((abs(el) for el in arr))
	diff = 0
	for q in queries:
		diff += q
		tot += pos_size * q - neg_size * q
		if q > 0:
			while neg_size and negative[-1][0] + diff >= 0:
				(n, count) = negative.pop()
				positive.append((n, count))
				pos_size += count
				neg_size -= count
				tot += abs(n + diff) * 2 * count
		else:
			while pos_size and positive[-1][0] + diff < 0:
				(n, count) = positive.pop()
				negative.append((n, count))
				neg_size += count
				pos_size -= count
				tot += abs(n + diff) * 2 * count
		yield tot
input()
arr = [int(s) for s in input().split()]
input()
que = [int(s) for s in input().split()]
for res in q(arr, que):
	print(res)


from collections import Counter
a = int(input())
A = [int(x) for x in input().split()]
_ = int(input())
Q = [int(x) for x in input().split()]
neg_nums = [x for x in A if x < 0]
pos_nums = [x for x in A if x >= 0]
pos_size = len(pos_nums)
neg_size = len(neg_nums)
pos = list(reversed(sorted(Counter(pos_nums).items())))
neg = sorted(Counter(neg_nums).items())
sm = sum((abs(x) for x in A))
cumsm = 0
for q in Q:
	cumsm += q
	sm += pos_size * q - neg_size * q
	if q > 0:
		while neg_size and neg[-1][0] + cumsm >= 0:
			(n, count) = neg.pop()
			pos.append((n, count))
			pos_size += count
			neg_size -= count
			sm += abs(n + cumsm) * count * 2
	else:
		while pos_size and pos[-1][0] + cumsm < 0:
			(n, count) = pos.pop()
			neg.append((n, count))
			neg_size += count
			pos_size -= count
			sm += abs(n + cumsm) * count * 2
	print(sm)


import bisect
N = int(input())
array = [int(x) for x in input().split()]
total = sum(array)
first_i = [0]
array.sort()
for i in array:
	first_i.append(first_i[-1] + i)
Q = int(input())
queries = [int(x) for x in input().split()]
total_q = 0
for q in queries:
	total_q += q
	position = bisect.bisect_left(array, -total_q)
	print((N - position + 1 - (position + 1)) * total_q + total - first_i[position] - first_i[position])


import bisect
N = int(input())
a = list(map(int, input().split()))
Q = int(input())
b = list(map(int, input().split()))
a = sorted(a)
a_sum = [0] * len(a)
for k in range(len(a)):
	a_sum[k] = a[k] + a_sum[k - 1]
a_sum = [0] + a_sum
val = 0
for query in b:
	val += query
	index = bisect.bisect_left(a, -val)
	res = (N - index) * val + a_sum[-1] - a_sum[index]
	if val >= 0:
		res += abs(a_sum[index] + index * val)
	else:
		index2 = bisect.bisect_left(a, 0)
		res += abs(a_sum[index] - a_sum[index2] + val * (index - index2))
		res += abs(a_sum[index2] + index2 * val)
	print(res)


from bisect import *
from itertools import accumulate
n = int(input())
arr = sorted(list(map(int, input().split())))
arr_cumsum = [0]
arr_cumsum.extend(accumulate(arr))
start_sum = sum(map(abs, arr))
q = int(input())
queries = list(map(int, input().split()))
nof_negative = bisect_right(arr, 0)
nof_positive = len(arr) - bisect_left(arr, 0)
cache = dict()
x = 0
for inc in queries:
	curr_sum = start_sum
	x += inc
	if not x in cache:
		if x < 0:
			nof_greater = len(arr) - bisect_right(arr, -x)
			curr_sum += (nof_negative - nof_greater) * -x
			sum_between_neg_and_gr = arr_cumsum[len(arr) - nof_greater] - arr_cumsum[nof_negative]
			curr_sum -= 2 * sum_between_neg_and_gr + (len(arr) - nof_greater - nof_negative) * x
		elif x > 0:
			nof_lesser = bisect_left(arr, -x)
			curr_sum += (nof_positive - nof_lesser) * x
			sum_between_ls_and_pos = arr_cumsum[len(arr) - nof_positive] - arr_cumsum[nof_lesser]
			curr_sum += 2 * sum_between_ls_and_pos + (len(arr) - nof_positive - nof_lesser) * x
		cache[x] = curr_sum
	print(cache[x])


from bisect import bisect_left as bisect
(N, ar) = (int(input()), [int(x) for x in input().split()])
(Q, qr) = (int(input()), [int(x) for x in input().split()])
ar = sorted(ar)
Sc = [0]
for x in ar:
	Sc.append(x + Sc[-1])
q = 0
for x in qr:
	q += x
	n = bisect(ar, -q)
	print(Sc[-1] - 2 * Sc[n] + q * (N - 2 * n))


from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = list(map(int, input().split()))
nn = [x for x in a if x < 0]
nn.sort()
pp = [x for x in a if x >= 0]
pp.sort()
nc = len(nn)
pc = len(pp)
ns = sum(nn)
ps = sum(pp)
mx = -2000
mn = 2000
dp = []
dn = []
for i in range(mn + 2):
	dp.append([0, 0])
	dn.append([0, 0])
if len(pp):
	s = 0
	c = 0
	for i in range(len(pp)):
		if i == 0:
			t = [0, 0]
		elif pp[i] > pp[i - 1]:
			t = [i, s]
			c = i
		else:
			t = [c, dp[pp[i - 1]][1]]
		s += pp[i]
		dp[pp[i]] = t
	if len(pp) > 1:
		for j in range(pp[0] + 1, pp[1]):
			dp[j] = [1, pp[0]]
	for j in range(pp[-1] + 1, mn + 1):
		dp[j] = [i + 1, s]
	k = next((k for (k, x) in enumerate(dp) if x != [0, 0]))
	for j in range(mn, k, -1):
		if dp[j] == [0, 0]:
			dp[j] = dp[j + 1]
if len(nn):
	s = 0
	c = 0
	nn.reverse()
	for i in range(len(nn)):
		if nn[i] < nn[i - 1]:
			t = [i, s]
			c = i
		else:
			t = [c, dn[nn[i - 1]][1]]
		s += nn[i]
		if dn[-nn[i]] == [0, 0]:
			dn[-nn[i]] = t
	if len(nn) > 1:
		for j in range(-nn[0] + 1, -nn[1]):
			dn[j] = [1, nn[0]]
	for j in range(-nn[-1] + 1, mn + 1):
		dn[j] = [i + 1, s]
	k = next((k for (k, x) in enumerate(dn) if x != [0, 0]))
	for j in range(mn, k, -1):
		if dn[j] == [0, 0]:
			dn[j] = dn[j + 1]
aa = a[:]
xx = 0
for x in b:
	xx += x
	nns = ns
	pps = ps
	if xx < 0:
		i = max(xx, mx)
		nns = ns + (nc + dp[-i][0]) * xx + dp[-i][1]
		pps = ps + (pc - dp[-i][0]) * xx - dp[-i][1]
	elif xx > 0:
		i = min(xx, mn)
		nns = ns + (nc - dn[i][0]) * xx - dn[i][1]
		pps = ps + (pc + dn[i][0]) * xx + dn[i][1]
	print(abs(pps) + abs(nns))


from collections import Counter
n = int(input().strip())
a = [int(x) for x in input().strip().split(' ')]
q = int(input().strip())
z = [int(x) for x in input().strip().split(' ')]
posn = [x for x in a if x >= 0]
negn = [x for x in a if x < 0]
poss = len(posn)
negs = len(negn)
pl = list(reversed(sorted(Counter(posn).items())))
nl = sorted(Counter(negn).items())
ctotal = sum((abs(x) for x in a))
cdiff = 0
for x in z:
	cdiff += x
	ctotal += poss * x - negs * x
	if x > 0:
		while negs and nl[-1][0] + cdiff >= 0:
			(num, numc) = nl.pop()
			pl.append((num, numc))
			poss += numc
			negs -= numc
			ctotal += abs(num + cdiff) * 2 * numc
	else:
		while poss and pl[-1][0] + cdiff < 0:
			(num, numc) = pl.pop()
			nl.append((num, numc))
			negs += numc
			poss -= numc
			ctotal += abs(num + cdiff) * 2 * numc
	print(ctotal)


from collections import Counter
n = int(input().strip())
a = [int(x) for x in input().strip().split(' ')]
q = int(input().strip())
z = [int(x) for x in input().strip().split(' ')]
posn = [x for x in a if x >= 0]
negn = [x for x in a if x < 0]
poss = len(posn)
negs = len(negn)
pl = list(reversed(sorted(Counter(posn).items())))
nl = sorted(Counter(negn).items())
ctotal = sum((abs(x) for x in a))
cdiff = 0
for x in z:
	cdiff += x
	ctotal += poss * x - negs * x
	if x > 0:
		while negs and nl[-1][0] + cdiff >= 0:
			(num, numc) = nl.pop()
			pl.append((num, numc))
			poss += numc
			negs -= numc
			ctotal += abs(num + cdiff) * 2 * numc
	else:
		while poss and pl[-1][0] + cdiff < 0:
			(num, numc) = pl.pop()
			nl.append((num, numc))
			negs += numc
			poss -= numc
			ctotal += abs(num + cdiff) * 2 * numc
	print(ctotal)


import collections

def bin_search(arr, left, right, target):
	while left <= right:
		mid = (left + right) // 2
		midval = arr[mid]
		if midval == target:
			return mid
		elif midval > target:
			right = mid - 1
		else:
			left = mid + 1
	return mid

def sum_query(arr, queries):
	n = len(arr)
	(min_val, max_val) = (min(arr), max(arr))
	C = collections.Counter(arr)
	precal_results_index = sorted(C.keys())
	c_sum = sum(arr) - n * min_val
	np = len(precal_results_index)
	precal_results = [None] * np
	left_num = C[precal_results_index[0]]
	right_num = n - left_num
	precal_results[0] = (c_sum, left_num, right_num)
	for i in range(1, np):
		diff = precal_results_index[i] - precal_results_index[i - 1]
		c_sum += -right_num * diff + left_num * diff
		c_count = C[precal_results_index[i]]
		right_num -= c_count
		left_num += c_count
		precal_results[i] = (c_sum, left_num, right_num)
	m = len(queries)
	partial_sum = [0] * m
	c_sum = 0
	for i in range(m):
		c_sum += queries[i]
		partial_sum[i] = c_sum
	for psum in partial_sum:
		p0 = -psum
		if p0 > max_val:
			print(precal_results[-1][0] + n * (p0 - max_val))
		elif p0 < min_val:
			print(precal_results[0][0] + n * (min_val - p0))
		else:
			index = bin_search(precal_results_index, 0, np - 1, p0)
			if precal_results_index[index] == p0:
				print(precal_results[index][0])
			elif precal_results_index[index] < p0:
				print(precal_results[index][0] + (p0 - precal_results_index[index]) * (precal_results[index][1] - precal_results[index][2]))
			else:
				print(precal_results[index][0] + (precal_results_index[index] - p0) * (precal_results[index][2] - precal_results[index][1] + 2 * C[precal_results_index[index]]))
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
sum_query(arr, queries)


import bisect
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [int(x) for x in input().split()]
A.sort()
sums = [0] * N
sums[0] = sum(A) - N * A[0]
for i in range(1, N):
	diff = A[i] - A[i - 1]
	sums[i] = sums[i - 1] - (N - i) * diff + i * diff
Qsum = 0
for q in range(Q):
	Qsum -= B[q]
	if Qsum <= A[0]:
		print(sums[0] + (A[0] - Qsum) * N)
	else:
		i = bisect.bisect_left(A, Qsum)
		diff = Qsum - A[i - 1]
		print(sums[i - 1] + diff * i - diff * (N - i))


from itertools import accumulate
from bisect import bisect_left
N = int(input().strip())
s = sorted(map(int, input().strip().split()))
acc = [0] + list(accumulate(s))
offset = 0
input()
for i in map(int, input().strip().split()):
	offset += i
	k = bisect_left(s, -offset)
	print(acc[-1] - 2 * acc[k] + (N - 2 * k) * offset)


import bisect
n = int(input().strip())
a = [int(elem) for elem in input().split()]
m = int(input().strip())
queries = [int(elem) for elem in input().split()]
a.sort()
sum_a = [a[0]]
for i in range(1, n):
	sum_a.append(sum_a[i - 1] + a[i])
tot_sum = sum_a[-1]
min_a = a[0]
max_a = a[-1]
sum_q = 0
for k in range(m):
	sum_q += queries[k]
	idx = bisect.bisect(a, -sum_q)
	if idx == 0:
		print(tot_sum + n * sum_q)
	elif idx == n:
		print(-(tot_sum + n * sum_q))
	else:
		print((n - 2 * idx) * sum_q + tot_sum - 2 * sum_a[idx - 1])


import array
na = int(input())
counts = array.array('L', [0] * 4001)
for x in input().split():
	counts[int(x) + 2000] += 1
ccounts = array.array('L', [0] * 4001)
acounts = array.array('L', [0] * 4001)
(tc, ta) = (0, 0)
for a in range(4001):
	tc += counts[a]
	ta += counts[a] * abs(a - 2000)
	ccounts[a] = tc
	acounts[a] = ta

def mcost(m):

	def c_in_range(ar, l, u):
		if u < -2000 or l > 2000:
			return 0
		l = l + 2000 - 1
		u = u + 2000
		low = 0 if l < 0 else ar[l]
		high = ar[-1] if u > 4000 else ar[u]
		return high - low
	out = 0
	if m >= 0:
		out += c_in_range(acounts, 0, 2000) + m * c_in_range(ccounts, 0, 2000)
		out += -c_in_range(acounts, -m, -1) + m * c_in_range(ccounts, -m, -1)
		out += +c_in_range(acounts, -2000, -m - 1) - m * c_in_range(ccounts, -2000, -m - 1)
	else:
		out += c_in_range(acounts, -2000, 0) + abs(m) * c_in_range(ccounts, -2000, 0)
		out += -c_in_range(acounts, 1, abs(m)) + abs(m) * c_in_range(ccounts, 1, abs(m))
		out += +c_in_range(acounts, abs(m) + 1, 2000) - abs(m) * c_in_range(ccounts, abs(m) + 1, 2000)
	return out
s = ''
m = 0
nq = int(input())
for q in input().split():
	m += int(q)
	cost = mcost(m)
	s += str(cost) + '\n'
print(s, end='')


from collections import Counter

def q(arr, queries):
	positive_n = [el for el in arr if el >= 0]
	negative_n = [el for el in arr if el < 0]
	pos_size = len(positive_n)
	neg_size = len(negative_n)
	positive = list(reversed(sorted(Counter(positive_n).items())))
	negative = sorted(Counter(negative_n).items())
	tot = sum((abs(el) for el in arr))
	diff = 0
	for q in queries:
		diff += q
		tot += pos_size * q - neg_size * q
		if q > 0:
			while neg_size and negative[-1][0] + diff >= 0:
				(n, count) = negative.pop()
				positive.append((n, count))
				pos_size += count
				neg_size -= count
				tot += abs(n + diff) * 2 * count
		else:
			while pos_size and positive[-1][0] + diff < 0:
				(n, count) = positive.pop()
				negative.append((n, count))
				neg_size += count
				pos_size -= count
				tot += abs(n + diff) * 2 * count
		yield tot
input()
arr = [int(s) for s in input().split()]
input()
que = [int(s) for s in input().split()]
for res in q(arr, que):
	print(res)


n = int(input())
a = [int(x) for x in input().split()]
m = int(input())
b = [int(x) for x in input().split()]
a.sort()
s = [0]
for x in a:
	s.append(s[-1] + x)

def find(x):
	(l, r) = (0, len(a))
	while l < r:
		m = (l + r) // 2
		if x > a[m]:
			l = m + 1
		else:
			r = m
	return l

def solve(x):
	l = find(0)
	r = find(-x)
	(l, r) = (min(l, r), max(l, r))
	result = abs(s[l] + x * l) + abs(s[r] - s[l] + x * (r - l)) + abs(s[-1] - s[r] + x * (n - r))
	return result
xsum = 0
for x in b:
	xsum += x
	print(solve(xsum))


from collections import Counter
from bisect import bisect_left
N = input()
C = Counter(map(int, input().split()))
A = sorted([[k, v] for (k, v) in C.items()])
ind_0 = bisect_left(A, [0, 0])
B = [0] + [abs(k) * v for (k, v) in A]
for j in range(len(B) - 1):
	B[j + 1] += B[j]
C = [0] + [v for (k, v) in A]
for j in range(len(C) - 1):
	C[j + 1] += C[j]
last_sum = B[-1]
Q = input()
X = map(int, input().split())
xc = 0
for x in X:
	xc += x
	if xc > 0:
		ind_xc = bisect_left(A, [-xc, 0])
		s1 = B[-1] - B[ind_0] + (C[-1] - C[ind_0]) * xc
		s2 = B[ind_0] - B[ind_xc] - (C[ind_0] - C[ind_xc]) * xc
		s3 = B[ind_xc] - C[ind_xc] * xc
		s = s1 - s2 + s3
	elif xc < 0:
		ind_xc = bisect_left(A, [-xc, 0])
		s1 = B[ind_0] - C[ind_0] * xc
		s2 = B[ind_xc] - B[ind_0] + (C[ind_xc] - C[ind_0]) * xc
		s3 = B[-1] - B[ind_xc] + (C[-1] - C[ind_xc]) * xc
		s = s1 - s2 + s3
	else:
		s = B[-1]
	print(s)


import bisect
n = int(input().strip())
A = [int(m) for m in input().strip().split()]
input()
Q = [int(m) for m in input().strip().split()]
A.sort()
CumSum = [A[0]]
for i in A[1:]:
	CumSum.append(i + CumSum[-1])
SumAbs = sum([abs(m) for m in A])
AddFactor = 0
for (I, i) in enumerate(Q):
	AddFactor += i
	if AddFactor > 0:
		SplitLoc1 = bisect.bisect_right(A, -AddFactor)
		SplitLoc2 = bisect.bisect_left(A, 0)
		Mult = 1
	elif AddFactor < 0:
		SplitLoc2 = bisect.bisect_left(A, -AddFactor)
		SplitLoc1 = bisect.bisect_right(A, 0)
		Mult = -1
	elif AddFactor == 0:
		SplitLoc1 = -1
	if SplitLoc1 == -1:
		print(SumAbs)
	else:
		if SplitLoc1 == 0:
			CSLeft = 0
		else:
			CSLeft = CumSum[SplitLoc1 - 1]
		MiddleChange = Mult * ((SplitLoc2 - SplitLoc1) * AddFactor + 2 * (CumSum[max([0, SplitLoc2 - 1])] - CSLeft))
		LeftChange = -AddFactor * SplitLoc1
		RightChange = AddFactor * max([0, n - SplitLoc2])
		TotalChange = LeftChange + MiddleChange + RightChange
		Output = SumAbs + TotalChange
		print(Output)


import bisect

def read_line_f():
	global f
	return f.readline()

def read_line():
	return input()

def read_ints():
	return [int(to_convert) for to_convert in read_line().strip().split(' ')]
_dummy_ = read_ints()
c = read_ints()
n = len(c)
d = 0
_dummy_ = read_ints()
x = read_ints()
count_x = {}
for item in c:
	if item not in count_x:
		count_x[item] = 1
	else:
		count_x[item] += 1
c = [x for x in count_x.keys()]
c.sort()
count_less_than_x = {}
sum_less = 0
for item in c:
	count_less_than_x[item] = sum_less
	sum_less += count_x[item]
less_than_zero = bisect.bisect_right(c, 0)
s = 0
for i in range(less_than_zero):
	s += -c[i] * count_x[c[i]]
for i in range(less_than_zero, len(c)):
	s += c[i] * count_x[c[i]]
rc = []
min_c = c[0]
max_c = c[-1]
len_c = len(c)
result = 0
for v in x:
	prev_d = d
	d += v
	if prev_d + min_c > 0 and d + min_c > 0:
		result += n * v
	elif prev_d + max_c < 0 and d + max_c < 0:
		result += n * -v
	else:
		if d > 0:
			l = bisect.bisect_right(c, -d)
			r = bisect.bisect_left(c, 0)
		else:
			l = bisect.bisect_right(c, 0)
			r = bisect.bisect_left(c, -d)
		neg = 0
		s_switch = 0
		if l < len_c:
			ls = l
			if l > 0:
				neg = count_less_than_x[c[l]]
			if d < 0:
				while ls < r:
					num = c[ls]
					s_switch += (-d - num - num) * count_x[num]
					ls += 1
			else:
				while ls < r:
					num = c[ls]
					s_switch += (d + num + num) * count_x[c[ls]]
					ls += 1
		pos = 0
		if r < len_c:
			pos = n - count_less_than_x[c[r]]
		result = s + s_switch + d * (pos - neg)
	rc.append(result)
print(*rc, sep='\n')


n = int(input())
A = sorted((int(x) for x in input().split()))
C = [0]
for a in A:
	C.append(C[-1] + a)
nq = int(input())
Q = [int(x) for x in input().split()]

def bsearch(L, bias, x):
	a = 0
	b = len(L) - 1
	if x >= L[b] + bias:
		return len(L)
	if x < L[a] + bias:
		return 0
	while b - a > 1:
		c = (a + b) // 2
		if L[c] + bias <= x:
			a = c
		else:
			b = c
	return b
bias = 0
for q in Q:
	bias += q
	ix = bsearch(A, bias, 0)
	pos = C[-1] - C[ix] + (n - ix) * bias
	neg = C[ix] - C[0] + ix * bias
	print(pos - neg)


n = int(input())
A = sorted([int(x) for x in input().split()])
B = [a for a in A if a < 0]
A = [a for a in A if a >= 0]
glob = 0
n = len(A)
cumA = [0] * (n + 1)
for i in range(1, n + 1):
	cumA[i] = cumA[i - 1] + A[i - 1]
m = len(B)
cumB = [0] * (m + 1)
for i in range(1, m + 1):
	cumB[i] = cumB[i - 1] + B[i - 1]
q = int(input())
for x in [int(x) for x in input().split()]:
	glob += x
	summa = 0
	a = 0
	b = n
	while a < b:
		c = (a + b) // 2
		if A[c] + glob < 0:
			a = c + 1
		else:
			b = c
	t11 = cumA[n] - cumA[a] + glob * (n - a)
	t12 = -(cumA[a] + glob * a)
	a = 0
	b = m
	while a < b:
		c = (a + b) // 2
		if B[c] + glob < 0:
			a = c + 1
		else:
			b = c
	t21 = cumB[m] - cumB[b] + glob * (m - b)
	t22 = -(cumB[b] + glob * b)
	summa = t11 + t12 + t21 + t22
	print(summa)


n = int(input().strip())
a = list(map(int, input().strip().split()))
q = int(input().strip())
qv = map(int, input().strip().split())
qrsumv = []
rsum = 0
for x in qv:
	rsum += x
	qrsumv.append(rsum)
a.sort()
arsumv = []
rsum = 0
for ai in a:
	rsum += ai
	arsumv.append(rsum)
for xri in qrsumv:
	low = 0
	high = n - 1
	while high >= low:
		mid = (low + high) // 2
		if a[mid] > -xri:
			high = mid - 1
		elif a[mid] < -xri:
			low = mid + 1
		else:
			break
	if high == mid - 1:
		mid -= 1
	arsumneg = arsumv[mid] if mid >= 0 else 0
	arsumpos = arsumv[-1] - arsumneg
	print(-arsumneg - (mid + 1) * xri + arsumpos + (n - mid - 1) * xri)


class TheThing:

	def __init__(self, array):
		self.array = array
		self.array.sort()
		self.array.reverse()
		self.num = len(self.array)
		self.leftSums = [0]
		for elem in array:
			self.leftSums.append(self.leftSums[-1] + elem)
		self.totalSum = self.leftSums[-1]
		self.rightSums = [self.totalSum - self.leftSums[i] for i in range(len(self.leftSums))]
		self.querySum = 0

	def AddQuery(self, query):
		i = self.FindIndex(query)
		self.querySum = self.querySum + query
		return self.leftSums[i] - self.rightSums[i] + (2 * i - self.num) * self.querySum

	def FindIndex(self, query):
		accumulatedQuery = self.querySum + query
		start = 0
		end = len(self.array)
		return self.BinaryFindIndex(start, end, accumulatedQuery)

	def BinaryFindIndex(self, start, end, test):
		if start == end:
			return start
		if start == end - 1:
			if self.array[end - 1] + test >= 0:
				return end
			else:
				return start
		candidate = (start + end) // 2
		if self.array[candidate - 1] + test >= 0:
			return self.BinaryFindIndex(candidate, end, test)
		return self.BinaryFindIndex(start, candidate, test)

def main():
	n = input().strip().split()
	array = [int(x) for x in input().strip().split()]
	num_queries = input().strip().split()
	queries = [int(x) for x in input().strip().split()]
	thing = TheThing(array)
	for q in queries:
		print(thing.AddQuery(q))
main()


import bisect
N = int(input())
A = list(map(int, input().strip().split(' ')))
count = [0 for i in range(4001)]
total = 0
for i in range(len(A)):
	count[A[i] + 2000] += 1
	total += A[i]
sub = []
subcount = []
temp = 0
tempp = 0
for i in range(4001):
	temp += i * count[i]
	tempp += count[i]
	sub += [temp]
	subcount += [tempp]
input()
Q = list(map(int, input().strip().split(' ')))
S = []
temp = 0
for i in range(len(Q)):
	temp += Q[i]
	S += [temp]
for i in range(len(S)):
	temp = 0
	s = S[i]
	if s >= 2000:
		print(total + N * s)
	elif s <= -2000:
		print(-total - N * s)
	else:
		temp = 0
		k = 2000 - s
		temp = total - 2 * sub[k] - k * (N - 2 * subcount[k]) + N * 2000
		print(temp)


from bisect import bisect_left
N = int(input())
array = list(map(int, input().strip().split(' ')))
Q = int(input())
queries = list(map(int, input().strip().split(' ')))
array = sorted(array)
sum_below = []
current_sum = 0
for elem in array:
	sum_below.append(current_sum)
	current_sum += elem
sum_below.append(current_sum)
sum_above = []
current_sum = sum(array)
for elem in array:
	sum_above.append(current_sum)
	current_sum -= elem
sum_above.append(current_sum)
relative_zero = 0
for q in queries:
	relative_zero -= q
	zero_location = bisect_left(array, relative_zero)
	below = sum_below[zero_location] - relative_zero * zero_location
	above = sum_above[zero_location] - relative_zero * (N - zero_location)
	print(abs(below) + abs(above))


def binarySearch(a, total):
	l = 0
	r = len(a)
	while r - l > 1:
		m = (l + r) // 2
		if a[m] + total >= 0:
			r = m
		else:
			l = m
	return l
n = int(input().strip())
a = sorted(list(map(int, input().strip().split())))
partial = [a[0]]
for i in range(1, n):
	partial.append(a[i] + partial[-1])
Q = int(input().strip())
q = list(map(int, input().strip().split()))
total = 0
for i in range(Q):
	total += q[i]
	index = binarySearch(a, total)
	leftSum = partial[index] + total * (index + 1)
	rightSum = partial[n - 1] - partial[index] + total * (n - index - 1)
	print(abs(leftSum) + rightSum)


def count_up_array(array, n_min, n_max):
	count_array = [0 for i in range(n_min, n_max + 1)]
	min_val = n_max + 1
	max_val = n_min - 1
	for i in range(0, len(array)):
		count_array[array[i]] += 1
	for j in range(n_min, n_max + 1):
		if count_array[j] != 0 and min_val == n_max + 1:
			min_val = j
		if count_array[-1 * j] != 0 and max_val == n_min - 1:
			max_val = -1 * j
	return (count_array, min_val, max_val)

def compute_shifted_abs_sum(counts, shift, n_min, n_max):
	total = 0
	for i in range(n_min, n_max + 1):
		total += abs(counts[i] * (i + shift))
	return total
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
queries_list = [int(a) for a in input().split()]
(counts, min_value, max_value) = count_up_array(A, -2000, 2000)
positive_computation = compute_shifted_abs_sum(counts, -1 * min_value, -2000, 2000)
negative_computation = compute_shifted_abs_sum(counts, -1 * max_value, -2000, 2000)
total_shift = 0
for i in range(0, len(queries_list)):
	total_shift += queries_list[i]
	if total_shift >= -1 * min_value:
		print(positive_computation + (total_shift + min_value) * N)
	elif total_shift <= -1 * max_value:
		print(negative_computation - (total_shift + max_value) * N)
	else:
		print(compute_shifted_abs_sum(counts, total_shift, -2000, 2000))


def prepareBook(arr):
	book = {x: {'n': 0, 'leftSum': 0, 'leftNums': 0, 'rightSum': 0, 'rightNums': 0} for x in range(-2001, 2002)}
	for num in arr:
		book[num]['n'] += 1
	leftSum = 0
	leftNums = 0
	for i in range(-2001, 2002):
		book[i]['leftSum'] = leftSum
		book[i]['leftNums'] = leftNums
		leftSum += book[i]['n'] * (i + 2000)
		leftNums += book[i]['n']
	rightSum = 0
	rightNums = 0
	for i in range(2001, -2002, -1):
		book[i]['rightSum'] = rightSum
		book[i]['rightNums'] = rightNums
		rightSum += book[i]['n'] * (2000 - i)
		rightNums += book[i]['n']
	return book

def calcSum(queries, book):
	center = 0
	for query in queries:
		center -= query
		if center < -2000:
			preRightSum = book[2001]['leftSum']
			rightSum = preRightSum + book[2001]['leftNums'] * (-center - 2000)
			print(rightSum)
		elif center > 2000:
			preLeftSum = book[-2001]['rightSum']
			leftSum = preLeftSum + book[-2001]['rightNums'] * (center - 2000)
			print(leftSum)
		else:
			preRightSum = book[2001]['leftSum'] - book[center + 1]['leftSum']
			rightSum = preRightSum - book[center]['rightNums'] * (2000 + center)
			preLeftSum = book[-2001]['rightSum'] - book[center - 1]['rightSum']
			leftSum = preLeftSum - book[center]['leftNums'] * (2000 - center)
			print(leftSum + rightSum)
n = int(input())
arr = list(map(int, input().strip().split(' ')))
book = prepareBook(arr)
numQueries = int(input())
queries = list(map(int, input().strip().split(' ')))
calcSum(queries, book)


import sys

def findFirstGE(ar, v):
	N = len(ar)
	if ar[0] >= v:
		return 0
	if ar[-1] < v:
		return -1
	sBegin = 0
	sEnd = N - 1
	while sBegin + 1 != sEnd:
		iMid = (sBegin + sEnd) // 2
		if ar[iMid] >= v:
			sEnd = iMid
		else:
			sBegin = iMid
	return sEnd

def getSumLT(arSum, i):
	if i < 0:
		return arSum[-1]
	if i == 0:
		return 0
	return arSum[i - 1]

def getSumGE(arSum, i):
	if i < 0:
		return 0
	if i == 0:
		return arSum[-1]
	return arSum[-1] - arSum[i - 1]
N = int(input().strip())
ar = list(map(int, input().strip().split(' ')))
ar.sort()
Q = int(input().strip())
qr = list(map(int, input().strip().split(' ')))
cumSum = [0] * N
cumSum[0] = ar[0]
for i in range(1, N):
	cumSum[i] = cumSum[i - 1] + ar[i]
totalAdded = 0
result = []
for q in qr:
	totalAdded += q
	i = findFirstGE(ar, -totalAdded)
	r = 0
	if i < 0:
		r = -(cumSum[-1] + N * totalAdded)
	else:
		r = -(getSumLT(cumSum, i) + i * totalAdded) + (getSumGE(cumSum, i) + (N - i) * totalAdded)
	result.append(r)
	print(r)


n = int(input().strip())
a = [int(x) for x in input().strip().split(' ')]
q = int(input().strip())
queries = [int(x) for x in input().strip().split(' ')]
for j in range(q - 1):
	queries[j + 1] = queries[j] + queries[j + 1]
counts = [0 for _ in range(4001)]
for entry in a:
	counts[entry + 2000] += 1
partsmsum = [0 for _ in range(4001)]
partsmct = [0 for _ in range(4001)]
partlgsum = [0 for _ in range(4001)]
partlgct = [0 for _ in range(4001)]
partsmsum[0] = -2000 * counts[0]
partsmct[0] = counts[0]
partlgsum[4000] = 0
partlgct[4000] = 0
for j in range(1, 4001):
	partsmsum[j] = partsmsum[j - 1] + (j - 2000) * counts[j]
	partsmct[j] = partsmct[j - 1] + counts[j]
	partlgsum[4000 - j] = partlgsum[4000 - j + 1] + (2000 - j + 1) * counts[4000 - j + 1]
	partlgct[4000 - j] = partlgct[4000 - j + 1] + counts[4000 - j + 1]
for j in queries:
	if j <= -2000:
		print(-partsmsum[4000] - j * n)
	if j >= 2000:
		print(partsmsum[4000] + j * n)
	if j > -2000 and j < 2000:
		print(-partsmsum[2000 - j] - j * partsmct[2000 - j] + partlgsum[2000 - j] + j * partlgct[2000 - j])


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


import sys
(low, high) = (-2000, 2000)

def count(arr):
	counts = [0] * (high - low + 1)
	for a in arr:
		counts[a - low] += 1
	return counts

def agg_sum(arr):
	arr_agg = arr[:]
	for i in range(1, len(arr)):
		arr_agg[i] = arr_agg[i - 1] + arr[i]
	return arr_agg

def count_leq(arr):
	arr_agg = arr[:]
	for i in reversed(range(0, len(arr) - 1)):
		arr_agg[i] = arr_agg[i + 1] + arr[i]
	return arr_agg

def count_gr(arr):
	arr_agg = [0] * len(arr)
	for i in range(1, len(arr)):
		arr_agg[i] = arr_agg[i - 1] + arr[i - 1]
	return arr_agg

def query(arr, q):
	result = 0
	for a in arr:
		result += abs(q + a)
	return result

def playingWithNumbers(arr, queries):
	c_neq = count([-a for a in arr])
	c_leq = count_leq(c_neq)
	c_gr = count_gr(c_neq)
	N = len(arr)
	Q = [0] * (high - low + 1)
	Q[low - low] = query(arr, low)
	for v in range(low + 1, high + 1):
		Q[v - low] = Q[v - 1 - low] - c_leq[v - low] + c_gr[v - low]
	q_agg = agg_sum(queries)
	for q in q_agg:
		if q < low:
			yield (Q[low - low] + (low - q) * N)
		elif q > high:
			yield (Q[high - low] + (q - high) * N)
		else:
			yield Q[q - low]
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
q = int(input().strip())
queries = list(map(int, input().strip().split(' ')))
result = playingWithNumbers(arr, queries)
print('\n'.join(map(str, result)))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


import sys

def playingWithNumbers(n, arr, queries):
	from itertools import accumulate

	def find(val, ln, arr):
		if arr[0] >= val:
			return 0
		if arr[-1] < val:
			return ln
		(st, i, end) = (0, ln // 2, ln)
		while i != 0 and arr[i - 1] >= val or arr[i] < val:
			if arr[i] < val:
				(st, i) = (i, (i + end) // 2)
			else:
				(end, i) = (i, (i + st) // 2)
		return i
	arr.sort()
	qtot = 0
	tot = sum((abs(i) for i in arr))
	zeroSt = find(0, n, arr)
	zeroEn = find(1, n, arr)
	out = []
	for q in queries:
		qtot += q
		adj = 0
		if qtot < 0:
			(st, end) = (zeroEn, find(-qtot + 1, n, arr))
			adj = qtot * (n - end) - qtot * st + sum((abs(i + qtot) - abs(i) for i in arr[st:end]))
		if qtot > 0:
			(st, end) = (find(-qtot, n, arr), zeroSt)
			adj = qtot * (n - end) - qtot * st + sum((abs(i + qtot) - abs(i) for i in arr[st:end]))
		out.append(tot + adj)
	return out
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = [n]
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


import math
import os
import random
import re
import sys
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


import math
import os
import random
import re
import sys
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


import math
import os
import random
import re
import sys
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


from bisect import bisect_left
n = int(input())
arr = [int(i) for i in input().split()]
(summer, f, arr) = (sum(arr), [0], sorted(arr))
for i in arr:
	f.append(f[-1] + i)
input()
q = [int(i) for i in input().split()]
t = 0
for i in q:
	t += i
	pos = bisect_left(arr, -t)
	print((n - pos + 1 - (pos + 1)) * t + summer - f[pos] - f[pos])


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


def playingWithNumbers(arr, queries):
	if arr[0] > 0:
		arr.insert(0, 0)
	pv = 0
	total = 0
	piv = search(0)
	sum_arr = arr[:]
	sm = 0
	a = arr[piv]
	for i in range(piv + 1, len(arr)):
		a += arr[i]
		sum_arr[i] = a
	a = arr[piv - 1]
	for i in range(piv - 2, -1, -1):
		a += arr[i]
		sum_arr[i] = a
	for i in range(len(queries)):
		sm += queries[i]
		if sm >= -arr[0]:
			total = sum_arr[-1] + sum_arr[0] + len(arr) * sm
			print(total)
			total = 0
			continue
		pv = search(-sm)
		if sm >= 0:
			if sum_arr[pv] > 0:
				gar = 0
			else:
				gar = sum_arr[pv]
			total += sum_arr[-1] + gar + (len(arr) - pv) * sm
			total += -(sum_arr[0] - gar) - pv * sm
		elif sm < 0:
			pv -= 1
			if sum_arr[pv] < 0:
				gar = 0
			else:
				gar = sum_arr[pv]
			total += sum_arr[-1] - gar + (len(arr) - pv - 1) * sm
			total += -(sum_arr[0] + gar) - (pv + 1) * sm
		print(total)
		total = 0

def search(x):
	l = 0
	r = len(arr)
	while l <= r:
		mid = l + (r - l) // 2
		if r - l <= 1:
			return r
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid
		else:
			r = mid
n = int(input())
arr = list(map(int, input().rstrip().split()))
arr.sort()
q = int(input())
queries = list(map(int, input().rstrip().split()))
playingWithNumbers(arr, queries)


import math
import os
import random
import re
import sys
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


import sys

def locate(val, lst):
	(lo, hi) = (0, len(lst))
	while lo < hi:
		mid = lo + hi >> 1
		if val > lst[mid]:
			lo = mid + 1
		else:
			hi = mid
	return hi

def absolute_elements_sum(line):
	N = int(next(line))
	arr = sorted(map(int, next(line).split()))
	z = [0]
	for c in arr:
		z.append(z[-1] + c)
	next(line)
	sol = []
	p = 0
	for c in map(int, next(line).split()):
		p += c
		i1 = locate(-p, arr)
		sol.append(z[-1] + p * (N - 2 * i1) - 2 * z[i1])
	print('\n'.join(map(str, sol)))
absolute_elements_sum(sys.stdin)


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))


n = int(input())
arr = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))
count = [0] * 4001
for i in arr:
	count[2000 + i] += 1
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
	sum_num_right.append(sum_num_right[i] - count[i])
sum_right = [0] * 4001
for i in range(4001):
	sum_right[0] += count[i] * i
for i in range(1, 4001):
	sum_right[i] = sum_right[i - 1] - sum_num_right[i]
sum_left = [0] * 4001
for i in range(4000, -1, -1):
	sum_left[4000] += count[i] * (4000 - i)
for i in range(3999, -1, -1):
	sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
acc = 0
for i in queries:
	acc += i
	mid = 2000 - acc
	if mid < 4001 and mid >= 0:
		print(sum_right[mid] + sum_left[mid])
	elif mid < 0:
		print(sum_right[0] + n * abs(mid))
	else:
		print(sum_left[4000] + n * (mid - 4000))