Make x a Mode

You are given a sequence \(a\) of length \(n\). In one operation you can increase any element of \(a\) by \(1\). You need to answer \(q\) queries. For each query, given an integer \(x\), determine the minimum total number of operations required so that, after some operations, there exists a sequence \(a'\) derived from \(a\) in which \(x\) is one of the modes (i.e. one of the values with maximum frequency).

Note: A sequence may have multiple modes.

Explanation:
Assume the original frequency of \(x\) is \(U\). You are allowed to increase elements which are less than \(x\) (each increase costs \(x-v\) if the element is \(v\)) so that they become \(x\). However, you cannot change elements already greater than \(x\) (since you may only increase numbers). Let the frequency of any number \(y\) be \(f(y)\). For an element \(y < x\) you have the option to convert some occurrences. Converting one occurrence not only increases the frequency of \(x\) by \(1\) but also decreases the frequency of \(y\) by \(1\) (a net swing of 2 for that group). Meanwhile, for any number \(y > x\) the frequency remains unchanged. Therefore, in order for \(x\) to be a mode in \(a'\) the following conditions must hold:

• \(U + T \ge f(y)\) for every \(y > x\) (since you cannot change those frequencies), and
• For every \(y < x\), if you convert \(m_y\) out of \(f(y)\) occurrences then the resulting frequency becomes \(f(y) - m_y\) and you need
  \(U + T \ge f(y) - m_y\). Because the conversion in group \(y\) gives a 2\(m_y\) swing relative to leaving them unchanged, it is enough to have
  \(2T \ge f(y) - U\) for the most critical group (where you devote all conversions to that group).

An optimal strategy is to perform operations only on those elements that are less than \(x\). Define the candidate pool as all indices with \(a_i < x\) (each candidate has a cost of \(x - a_i\)). Let \(T\) be the total number of conversions you choose. Then in order to ensure that in every group \(y\) (with \(y < x\)) after converting at least some elements the condition
\(U + T \ge f(y) - (\text{number of conversions chosen in group } y)\) holds,
a necessary condition per group is
\(T \ge \lceil (f(y) - U) / 2 \rceil\) for all \(y < x\) with \(f(y) > U\), and for all \(y > x\) we require
\(T \ge f(y) - U\). Hence, if we let

[ T_{req} = \max\Big{ \max_{y>x} (f(y)-U), ; \max_{y<x} \Big\lceil\frac{f(y)-U}{2}\Big\rceil \Big} ]

and if it is possible to choose \(T_{req}\) candidates from the pool (i.e. if the number of elements less than \(x\) is at least \(T_{req}\)), then the answer is the minimal total cost of selecting exactly \(T_{req}\) candidates subject to the following: for every group \(y < x\) the number of candidates selected from that group is at least

[ \max\Big{0, f(y) - (U+T_{req})\Big}. ]

The cost for each candidate from group \(y\) is \(x-y\). You must choose the forced conversions in each group and then, if needed, choose additional candidates (from anywhere in the candidate pool) with the smallest cost in order to reach a total of \(T_{req}\) conversions. If it is impossible, print \(-1\).

inputFormat

The first line contains two integers \(n\) and \(q\) (\(1 \le n, q \le 10^5\)). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(-10^9 \le a_i \le 10^9\). Then \(q\) lines follow, each containing a single integer \(x\) (\(-10^9 \le x \le 10^9\)) representing a query.

outputFormat

For each query, output the minimum number of operations required so that there exists a sequence \(a'\) in which \(x\) is one of the modes. If it is impossible, output \(-1\).

sample

5 3
1 2 2 1 3
1
2
3

0
0
1