Red-Blue Operations (Easy Version)
Contest: Educational Codeforces Round 148 (Rated for Div. 2)
Difficulty rating: 2100
Tags: binary search, greedy, implementation, math

The only difference between easy and hard versions is the maximum values of $$$n$$$ and $$$q$$$.

You are given an array, consisting of $$$n$$$ integers. Initially, all elements are red.

You can apply the following operation to the array multiple times. During the $$$i$$$-th operation, you select an element of the array; then:

- if the element is red, it increases by $$$i$$$ and becomes blue;
- if the element is blue, it decreases by $$$i$$$ and becomes red.

The operations are numbered from $$$1$$$, i. e. during the first operation some element is changed by $$$1$$$ and so on.

You are asked $$$q$$$ queries of the following form:

- given an integer $$$k$$$, what can the largest minimum in the array be if you apply exactly $$$k$$$ operations to it?

Note that the operations don't affect the array between queries, all queries are asked on the initial array $$$a$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 1000$$$) — the number of elements in the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains $$$q$$$ integers $$$k_1, k_2, \dots, k_q$$$ ($$$1 \le k_j \le 10^9$$$).

Output format:
For each query, print a single integer — the largest minimum that the array can have after you apply exactly $$$k$$$ operations to it.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4 10
5 2 8 4
1 2 3 4 5 6 7 8 9 10

Example output:
3 4 5 6 7 8 8 10 8 12

Example input:
5 10
5 2 8 4 4
1 2 3 4 5 6 7 8 9 10

Example output:
3 4 5 6 7 8 9 8 11 8

Editorial:
Let's try applying the operation to a single element multiple times. You can see that when you apply an operation an odd number of times, the element always gets larger. Alternatively, applying an operation an even amount of times always makes it smaller (or equal in case of $$$0$$$). Thus, generally, we would want to apply an odd number of operations to as many elements as we can.
Let's start by investigating an easy case: $$$k \le n$$$. Since there are so few operations, you can avoid subtracting from any element at all. Just one operation to each of $$$k$$$ elements. Which elements should get this operation? Obviously, $$$k$$$ smallest elements. If you don't pick at least one of them, it'll remain as the minimum of the array. If you do, the minimum will get larger than any of them. Another greedy idea is where to apply each operation to. We should add $$$k$$$ to the minimum element, $$$k-1$$$ to the second minimum and so on. You can show that it is always optimal by contradiction.
What if $$$k > n$$$? Then we have to subtract from some elements. First, recognize that there's no more than one element that will become smaller in the optimal answer. Consider an answer where at least two elements get smaller and move the later operation from one to another. Now both of them become larger.
Moreover, for parity reasons, if $$$k \bmod 2 = n \bmod 2$$$, you can increase all elements. Otherwise, you have to decrease exactly one.
Another greedy idea. You somewhat want the pair of operations (increase, decrease) to change the element as small as possible. In particular, you can always make the change equal to $$$-1$$$. To show it, you can look at some decreasing operation such that an increasing operation goes right before it and they are applied to different elements. You can swap them. They remain the same types. However, both elements get only larger. In the end, all adjacent increasing and decreasing operations go to the same element.
Now, let's think of the answer as the following sequence: adjacent pairs of (increase, decrease) and the separate increase operations that are applied no more than once to each element. Since all blocks do $$$-1$$$, only the values in the lone increase operations affect the answer value. Obviously, we would want these lone increases to be $$$k, k - 1, \dots, k - t$$$, where $$$t$$$ is the number of changed elements ($$$n-1$$$ or $$$n$$$). Once again, you can show that you can always rearrange the operations to obtain that.
Finally, the answer looks like this: add $$$k$$$ to the minimum, $$$k-1$$$ to the second minimum, $$$k - (n - (n + k) \bmod 2) - 1$$$ to the maximum or the second maximum depending on the parity. Before that, add $$$-1$$$ to some elements. Since we know where to apply the last operations, let's apply them first. Then we want to apply $$$-1$$$'s to make the minimum as large as possible. Well, we should always apply it to the current maximum. First, the minimum would remain as the original minimum. Then all elements will become equal to it at some point. Then we will be spreading the $$$-1$$$'s equally among the elements. So every $$$n$$$ additional operations, the minimum will be decreasing by $$$1$$$.
For the easy version, you can simulate this process. Sort the array, apply the last increase operations, find the minimum and the sum of the array, then calculate the result based on that. Let $$$a' = [a_1 + k, a_2 + k - 1, \dots]$$$. Let $$$s = \sum_{i = 1}^n (a' - \min a')$$$. Then the first $$$s$$$ operations of $$$-1$$$ will not change the minimum. The rest $$$\frac{k - (n - (n - k) \bmod 2)}{2} - s$$$ operations will decrease it by $$$1$$$ every $$$n$$$ operations. So it will get decreased by $$$\left\lceil\frac{\max(0, \frac{k - (n - (n - k) \bmod 2)}{2} - s)}{n}\right\rceil$$$.
Overall complexity: $$$O(n \cdot q \cdot \log n)$$$.