In the school computer room there are n servers which are responsible for processing…
- User
In the school computer room there are n servers which are responsible for processing several computing tasks. You know the number of scheduled tasks for each server: there are mi tasks assigned to the i-th server.
In order to balance the load for each server, you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. In other words you want to minimize expression ma - mb, where a is the most loaded server and b is the least loaded one.
In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another.
Write a program to find the minimum number of seconds needed to balance the load of servers. Input
The first line contains positive number n (1 ≤ n ≤ 105) — the number of the servers.
The second line contains the sequence of non-negative integers m1, m2, ..., mn (0 ≤ mi ≤ 2·104), where mi is the number of tasks assigned to the i-th server.
Output
Print the minimum number of seconds required to balance the load.
Examples
Input
2 1 6
Output
2
Input
7 10 11 10 11 10 11 11
Output
0
Input
5 1 2 3 4 5
Output
3
Note
In the first example two seconds are needed. In each second, a single task from server #2 should be moved to server #1. After two seconds there should be 3 tasks on server #1 and 4 tasks on server #2.
In the second example the load is already balanced.
A possible sequence of task movements for the third example is:
- move a task from server #4 to server #1 (the sequence m becomes: 2 2 3 3 5);
- then move task from server #5 to server #1 (the sequence m becomes: 3 2 3 3 4);
- then move task from server #5 to server #2 (the sequence m becomes: 3 3 3 3 3).
The above sequence is one of several possible ways to balance the load of servers in three seconds.
Assistant
We need to solve: given n up to 1e5, each mi up to 20000, we can move a task from one server to another in one second. We want to minimize the maximum difference (max - min) after any number of moves, and find the minimum number of moves needed to achieve that minimal possible difference. Actually the problem says: "you want to reassign some tasks to make the difference between the most loaded server and the least loaded server as small as possible. ... Write a program to find the minimum number of seconds needed to balance the load of servers." So we need to determine the minimum number of moves to achieve the minimal possible max-min.
But we need to be careful: The minimal possible max-min after reassigning tasks (allowing moving tasks arbitrarily) is either 0 or 1? Because total sum S = sum(mi) is fixed. We can redistribute tasks arbitrarily among n servers, but each move moves a single task; we can reassign tasks to any distribution as long as the total sum remains S. However, tasks are indivisible units (integers). The best we can do is to make all servers have either floor(S/n) or ceil(S/n) tasks. Then max - min = 0 if S divisible by n, else 1. So the minimal possible difference is either 0 or 1.
Thus the goal is: find minimum number of moves to achieve a distribution where each server has either k or k+1 tasks (k = floor(S/n)), with exactly (S mod n) servers having k+1 tasks (or maybe if S mod n = 0 then all have k). But is that the only possible distribution that minimizes max-min? Yes, because any distribution that achieves difference 0 (when S divisible by n) must have all equal to S/n; if not divisible, any distribution with max-min = 1 must have all values either floor or ceil, and the count of ceil must equal remainder. Also note that if S mod n = 0, we need all exactly S/n; difference 0. If S mod n != 0, difference 1 is the minimum.
But is it always possible to achieve that? Yes, by moving tasks. So the problem reduces to: Given initial multiset of numbers, find minimum number of moves (each move transfers 1 unit from one element to another) to reach a target multiset where all numbers are either k or k+1, with exactly r = S % n numbers being k+1 (and n - r numbers being k). This is a classic minimum number of transfers to achieve a target distribution, which equals the sum of positive deviations from target (or sum of negative deviations absolute value half?). Actually, if we consider moving tasks from servers that have more than target to those that have less, each move reduces the surplus by 1 and deficit by 1 simultaneously. The minimal number of moves is equal to the total surplus (i.e., sum over servers of max(0, mi - target_i)) because each move reduces surplus by 1. Equivalently, it is half the sum of absolute differences between initial and target, because each move reduces total absolute deviation by 2? Let's check: If we have target t_i (either k or k+1). Then for each i, define d_i = mi - t_i. Sum d_i = 0. The total number of moves needed is sum_{i: d_i > 0} d_i (or sum_{i: d_i < 0} -d_i). That's the minimum moves. Because each move transfers 1 from a positive to negative, reducing both by 1. Since sum positive = sum negative, the moves needed is exactly that sum. So the answer is simply that sum.
Thus we just need to compute k = floor(S/n), r = S % n. Then target: we need to decide which servers get k+1. To minimize moves, we should assign the k+1 target to those servers that currently have the highest values? Or does it matter? Because the target distribution is not uniquely defined: we must have exactly r servers with k+1 and the rest with k, but which servers get which can be chosen arbitrarily. The minimal total moves over all such assignments is what we want. So we need to choose which servers get the higher target to minimize sum|mi - t_i| or sum of surplus.
Thus we need to assign to exactly r servers a target of k+1, and to others target k. The cost for server i is |mi - t_i|, but total moves = sum_{i} (if mi > t_i, then mi - t_i; else t_i - mi? Actually, the total moves is sum_{i: mi > t_i} (mi - t_i) = sum_{i: mi < t_i} (t_i - mi). So we can minimize that sum by appropriately choosing which servers get the higher target. This is a simple assignment problem: we need to choose r servers to set target = k+1, the rest target = k, minimizing total absolute deviations? But since total surplus equals total deficit, the cost equals half sum |mi - t_i|, but we can minimize either. Equivalent to minimizing sum |mi - t_i|, because sum positive = sum negative, total moves = (sum |mi - t_i|)/2. However, it's easier to think: For each server i, if we assign target = k, the deviation is mi - k; if assign target = k+1, deviation is mi - (k+1). Since we need sum d_i = 0, we can think that we want the sum of positive deviations minimized. But we can directly compute the minimal total moves as follows: Sort the servers by mi. Then assign target = k to the smallest n - r servers, and target = k+1 to the largest r servers? Let's test. Intuitively, to minimize absolute deviations, we want to give the higher target to servers that already have higher loads, because then they need less increase or even have surplus. However, careful: If a server has a very high load, giving it target k+1 means its surplus is smaller than if given target k. So it reduces the positive deviation (or increases negative deviation if too low). Similarly, low load servers should get target k to reduce negative deviation. So indeed, the optimal assignment is to give the +1 to the r servers with the largest initial loads. But we must verify this yields minimum sum of absolute deviations? Let's analyze.
Let sorted m ascending: m[1] ≤ m[2] ≤ ... ≤ m[n]. Let k, r known. Suppose we decide that a set A of size r gets target = k+1, others get k. Then total moves = sum_{i in A} max(0, m_i - (k+1)) + sum_{i not in A} max(0, m_i - k) ??? Wait, we need to compute total surplus (i.e., sum of positive deviations). But positive deviations only arise if m_i > target; there could also be negative deviations if m_i < target. The total moves is the sum of positive deviations (which equals sum of absolute negative deviations). However, when computing total moves, we need to consider the amount of tasks that must be moved from surplus to deficit. That is exactly sum_{i: m_i > target_i} (m_i - target_i). If we assign target in a certain way, this sum might be minimized. But is it equivalent to minimizing sum of absolute differences? Since total moves = (1/2) * sum |m_i - target_i|, and sum |m_i - target_i| is minimized when we assign target appropriately. So yes, minimize sum absolute deviations. So we need to choose which servers get +1 to minimize sum |m_i - t_i|. Since t_i can be either k or k+1, for each i we have two possible costs: |m_i - k| and |m_i - (k+1)|. The problem is to choose exactly r indices to assign cost = |m_i - (k+1)|, and the rest cost = |m_i - k|, minimizing total cost. This is a selection problem: choose r indices where the "gain" of assigning k+1 instead of k is largest negative? Actually, define delta_i = |m_i - k| - |m_i - (k+1)|. If we assign k+1 instead of k to server i, the cost changes by -delta_i (since new cost is |m_i-(k+1)| = |m_i-k| - delta_i). So we want to choose r indices to assign k+1 that maximize total reduction (or minimize total cost). So we should pick the r indices with largest delta_i, because that reduces the total cost the most. So we need to compute delta_i.
Let's compute delta_i. Consider integer m_i and integer k. Then:
|m_i - k| - |m_i - (k+1)|.
We can analyze by cases.
If m_i ≤ k: then |m_i - k| = k - m_i, |m_i - (k+1)| = (k+1) - m_i = k - m_i + 1. So difference = (k - m_i) - (k - m_i + 1) = -1. So delta_i = -1.
If m_i ≥ k+1: then |m_i - k| = m_i - k, |m_i - (k+1)| = m_i - (k+1) = m_i - k - 1. So difference = (m_i - k) - (m_i - k - 1) = 1. So delta_i = 1.
If m_i = k: then case m_i ≤ k? Actually k is integer, m_i = k: then m_i ≤ k => delta = -1? Check: |k - k| = 0, |k - (k+1)| = 1, so 0-1 = -1. Yes.
If m_i = k+1: then m_i ≥ k+1 => |(k+1)-k| = 1, |(k+1)-(k+1)| = 0, difference = 1. So delta = 1.
Thus delta_i is -1 for m_i ≤ k, and +1 for m_i ≥ k+1. So delta_i is simply -1 for values <= k, +1 for values >= k+1.
Therefore, the reduction in total cost if we assign k+1 instead of k to server i is delta_i (since new cost = old cost - delta_i). Actually old cost is |m_i - k|, new cost is |m_i - (k+1)| = |m_i - k| - delta_i? Because delta = old - new => new = old - delta. So if delta positive, new cost is lower by that amount; if delta negative, new cost is higher (since delta negative => new = old - negative = old + |delta|). So we want to choose r servers to assign k+1 such that total cost is minimized, i.e., we want to maximize total reduction (sum of delta_i over chosen). Since delta_i are either -1 or +1, we want to pick servers with delta_i = +1 (i.e., m_i ≥ k+1) as many as possible, and avoid those with delta_i = -1. Because picking a server with delta = +1 reduces total cost by 1; picking one with delta = -1 increases total cost by 1.
But we must pick exactly r servers. To minimize total cost, we should choose r servers with the largest delta_i, which are those with delta_i = +1. If there are at least r servers with m_i ≥ k+1, then we can pick r of them, all with delta = +1, and total reduction = r. If there are fewer than r such servers, say count_high = H (where H = number of servers with m_i ≥ k+1), then we must pick all H of them (delta = +1 each), and the remaining r-H servers must be chosen from those with m_i ≤ k (delta = -1). Then total reduction = H1 + (r-H)(-1) = 2H - r. That's the maximum possible reduction given we must pick exactly r.
But wait, does the choice among those with m_i ≤ k matter? Since all have delta = -1, any selection yields same reduction. Similarly, among m_i ≥ k+1, all delta = +1. So the minimal total cost is:
Total cost if we assign all k (i.e., baseline) = sum_i |m_i - k|, call C0. Then the minimal total cost = C0 - max_reduction.
Then the minimal number of moves = (min_total_cost)/2? Because total moves = sum positive deviations = (sum absolute deviations)/2. But careful: The total moves is not exactly half of sum absolute deviations? Let's verify. Suppose we have target t_i, and deviations d_i = m_i - t_i, sum d_i = 0. The sum of positive d_i = total surplus. The sum of absolute deviations = sum |d_i| = 2 * total surplus (since total surplus = total deficit). So total moves = total surplus = (sum |d_i|)/2. Yes. So if we find minimal sum |d_i|, then answer = (min_sum_abs) / 2.
But we can compute the answer directly as total surplus: sum_{i: m_i > t_i} (m_i - t_i) for the optimal assignment. Possibly easier: The minimal moves is simply the total amount of tasks that must be taken from servers that have more than their target, which is the sum of excess. And the optimal assignment will minimize that total excess. So we can compute directly.
Let's derive a formula. Let k = floor(S/n), r = S % n. The optimal assignment: assign target = k+1 to some r servers. To minimize moves, we should give the +1 to the servers with the highest initial loads, because then they may have less excess (or even deficit). But does that align with the delta analysis? Yes: The servers with m_i ≥ k+1 are candidates for +1; they might have excess if m_i > k+1, or perfect if m_i = k+1. But if we give them +1, we reduce excess if they were above k+1? Actually if m_i > k+1, then with target k, excess = m_i - k; with target k+1, excess = m_i - (k+1) = (m_i - k) - 1, so excess decreases by 1. For m_i = k+1, excess becomes 0 from 1, also reduction by 1. For m_i = k, if we give target k+1, then we create a deficit of 1 (negative deviation), meaning we need to add a task to that server; from the perspective of excess, that server now contributes 0 excess (since it's below target) but the deficit will be covered by tasks from others. The total surplus (sum of positive deviations) will change: originally, with target k, server with m_i = k has excess 0. With target k+1, it has deficit 1, so it doesn't add to surplus; but also we need to supply that deficit from other servers, so the total surplus needed from others is unchanged? Actually total surplus must equal total deficit. Changing target from k to k+1 for a server may affect both surplus and deficit. For m_i = k, initially excess 0, deficit 0. After change, deficit 1. So total deficit increases by 1, thus total surplus must also increase by 1 to cover it. That means some other server's excess must be larger? But we are reassigning targets, not moving tasks yet. However, the total sum of absolute deviations changes. So the total moves is half of total absolute deviations. So our objective is to minimize total absolute deviations.
Given the delta analysis, we concluded that picking servers with m_i ≥ k+1 gives delta = +1 (i.e., reduces absolute deviation by 1 compared to baseline) and picking servers with m_i ≤ k gives delta = -1 (increases absolute deviation by 1). So the minimal total absolute deviation is C0 - max_reduction, where C0 = sum_i |m_i - k|, and max_reduction = min(r, H)*? Actually, max reduction = if H >= r then we pick r high servers, each giving +1 reduction, so total reduction = r; else we pick all H high servers (+H) and the rest (r-H) low servers give -1 each, so total reduction = H - (r-H) = 2H - r. So max_reduction = if H >= r: r; else: 2H - r.
Thus minimal sum_abs = C0 - max_reduction.
But is C0 = sum |m_i - k|? However, note that C0 is computed with all targets as k, but that baseline distribution does not necessarily satisfy sum target = S (since sum of k is n*k which may be less than S). But we're using it as a reference; the actual assignment must have exactly r servers at k+1. The delta approach gave us the minimal sum_abs. So answer = (C0 - max_reduction)/2.
But we can also compute answer directly as total excess after optimal assignment. Another way: Let's sort m. Then we can compute the cumulative sums and find the number of servers that should have k+1 vs k. But the minimal moves can be computed as the sum of excess of those above their target.
Let’s think of it as: we want to achieve final loads all between k and k+1. The total number of tasks is S. The final loads: some are k, some k+1. The minimal number of moves is the amount of tasks that must be moved from servers that have more than their final target. If we decide which servers are to be final high, we can compute excess sum.
An equivalent approach: The minimal moves equals the sum over all servers of max(0, m_i - target_i) for the optimal target assignment. And we can determine that by sorting and taking the highest r as high targets.
So let's sort m in non-decreasing order. Then assign: the smallest n-r servers get target k, the largest r servers get target k+1. Then compute sum_{i} max(0, m_i - target_i). Since for small servers, target = k; for large servers, target = k+1. But careful: Some of the largest r may actually have m_i < k+1 (i.e., they are below the target). Then max(0, m_i - (k+1)) = 0, but they would have deficit. The total surplus we compute would be only from servers with m_i > target. That is fine. But the sum of positive deviations would be computed correctly; however, does that equal the total moves? Yes, because the sum of positive deviations must equal sum of deficits. However, we need to ensure that the assignment of which servers get the +1 is indeed optimal. As per delta analysis, picking the largest r servers is optimal because they are the ones with m_i ≥ k+1? Actually, not necessarily; if there are fewer than r servers with m_i ≥ k+1, then among the largest r servers, some will have m_i ≤ k. In that case, it's still optimal to assign +1 to the largest r because we must assign exactly r servers to +1, and assigning +1 to any server with m_i ≤ k is equally bad (delta = -1). But does it matter which of the low servers we pick? Since all have delta -1, any set of low servers will have same effect. So picking the largest r servers (which include all high servers and then the highest among low? But if there are fewer than r high servers, the largest r servers will include all high servers and then the next highest low servers. Since all low servers have m_i ≤ k, and they all yield delta -1, it doesn't matter which low ones we pick. However, might there be a nuance: among low servers, those with m_i closer to k have smaller absolute deviation when assigned k+1? Let's compute the absolute deviation for low servers when assigned k+1: |m_i - (k+1)| = k+1 - m_i. If we assign k to them: |m_i - k| = k - m_i. The difference is (k - m_i) - (k+1 - m_i) = -1, regardless of m_i. So indeed for any m_i ≤ k, the cost increase is exactly 1 when switching from k to k+1, independent of m_i's value. Similarly for high servers (m_i ≥ k+1), the cost decrease is exactly 1. So delta_i = +1 for m_i ≥ k+1, -1 for m_i ≤ k. So the only distinguishing factor is whether m_i is >= k+1 or not. Therefore, the optimal set to assign +1 is to take all servers with m_i ≥ k+1 (they give benefit) and then if we still need more, arbitrarily pick some from m_i ≤ k (which will give penalty). The penalty per needed extra is 1. So indeed the selection of which low servers to give +1 does not matter; any set yields the same total absolute deviation.
Thus we can compute minimal sum_abs = C0 - (if H >= r then r else 2H - r). And answer = minimal sum_abs / 2.
But is it always integer? Since sum_abs will be even? Because sum of deviations d_i sum to 0, sum_abs is even? Possibly not: Suppose we have numbers: m = [0, 2], n=2, S=2, k=1, r=0? Actually r = 0 because 2%2=0. Then target all 1. C0 = |0-1|+|2-1| = 1+1=2, sum_abs=2, answer=1. That's integer. If r != 0, e.g., n=3, m=[0,0,3], S=3, k=1, r=0? 3%3=0, k=1, all target 1. C0 = 1+1+2=4, answer=2. That's integer. For r=1, say n=3, m=[0,0,2], S=2, k=0 (since 2/3 floor 0), r=2? Actually S=2, n=3 => k=0, r=2? Because 2%3=2. So k=0, r=2. Then target: two servers get 1, one gets 0. Minimal sum_abs? Compute. C0 = sum |mi - 0| = 0+0+2=2. H = number with mi >= k+1 = mi>=1? Only the server with 2 qualifies, so H=1. Since H < r, max_reduction = 21 - 2 = 0. So min_sum_abs = 2 - 0 = 2, answer=1. Let's check: We need two servers to have 1 and one to have 0. If we give +1 to the two smallest (0 and 0), then targets: 1,1,0? Actually we need exactly 2 servers with 1. So we could assign: server 0 ->1, server 0->1, server2->0. Then deviations: 0->1 (deficit 1), 0->1 (deficit 1), 2->0 (excess 2). Sum absolute = 1+1+2=4, answer=2. Not optimal. If assign +1 to the high server (2) and one low server (0): targets: 2->1? Actually high server gets +1? Wait, target for high server: if we assign it to have 1 (since +1) and low server also 1, and the other low server 0. Then deviations: server 2: 2-1=1 (excess 1); low server assigned 1: 0-1=-1 (deficit 1); other low server assigned 0: 0-0=0. Sum absolute = 1+1+0=2, answer=1. So indeed optimal is to assign +1 to the high server and one low server. In this case, H=1, we must pick all high servers, and then need to pick r-H = 1 low server. So total reduction = H1 + (r-H)*(-1) = 1-1=0, as computed. So sum_abs = C0 - 0 = 2, answer=1. That matches. So our formula works.
Thus answer = (C0 - max_reduction) / 2.
But we can also compute answer directly by sum of excess for the optimal assignment. Let's derive that.
Given sorted m, and we assign target = k for indices 1..n-r, and target = k+1 for indices n-r+1..n (largest r). Then total moves = sum_{i=1}^{n} max(0, m_i - target_i). But careful: For the largest r, target = k+1, so if m_i < k+1, then max(0, ...) = 0, but they may have deficit; the total surplus is only from those with m_i > target. The total moves should be equal to sum of surplus. This sum of surplus can also be computed as sum_{i: m_i > target_i} (m_i - target_i). That is correct. But we need to ensure that total surplus equals total deficit, but we don't need to compute deficit. So answer = sum_{i} max(0, m_i - target_i). However, is it guaranteed that for the optimal assignment the sum of surplus computed this way equals the minimal moves? Yes, because that sum is exactly the total amount of tasks that must be moved, and it's minimal across all assignments of targets that satisfy the sum constraint.
Thus we can compute answer as: Let k = S div n, r = S mod n. Sort m. For i from 0 to n-1 (0-index), if i < n-r, target = k; else target = k+1. Then compute ans = sum_{i} max(0, m_i - target). But is this always correct? Let's test with the earlier example: n=3, m=[0,0,2], S=2, k=0, r=2? Actually S=2, n=3 => k=0, r=2. Then n-r = 1. Sorted m = [0,0,2]. Assign: i=0 (<1) target=0; i=1 (>=1) target=1? Wait n-r = 1, so indices 0 to 0 get k=0, indices 1..2 get k+1=1. So targets: [0,1,1]. Then compute max(0, m - target): for 0: 0-0=0; for 0: 0-1 negative =>0; for 2: 2-1=1. Sum=1. That matches answer=1. Good.
Test with example 1: n=2, m=[1,6], S=7, k=3, r=1 (since 7%2=1). n-r=1. Sorted: [1,6]. targets: index0 (<1) target=3; index1 target=4? Actually k+1 = 4. So [3,4]. Compute max(0,1-3)=0; max(0,6-4)=2. Sum=2. Answer=2. Good.
Example 2: n=7, m=[10,11,10,11,10,11,11], S=74? Let's compute: 10+11+10+11+10+11+11 = 74? Actually sum= 10+11=21, +10=31, +11=42, +10=52, +11=63, +11=74. n=7, average = 10.571..., k=10, r=4 (since 74%7=4). n-r=3. Sorted m: [10,10,10,11,11,11,11]. Assign: first 3 -> target=10; last 4 -> target=11. Compute excess: for 10: 0; 10:0; 10:0; for 11: 0 (11-11=0); all 0. Sum=0. Good.
Example 3: n=5, m=[1,2,3,4,5], S=15, k=3, r=0 (since 15%5=0). n-r=5. Targets all =3. Excess: max(0,1-3)=0; 2-3=0; 3-3=0; 4-3=1;5-3=2; sum=3. Answer=3. Good.
So this direct method works: answer = sum_{i} max(0, m_i - target_i) where targets assigned as described.
But we need to be careful about the case where some servers are assigned target = k+1 but they have m_i less than k+1; then they contribute 0 to surplus, but the total deficit will be accounted for by the fact that total surplus equals total deficit; and we are correctly computing the moves as surplus. So yes.
Now the algorithm: Input n, list m. Compute sum S. Compute k = S // n, r = S % n. Sort m. Then for i in 0..n-1: if i < n - r: target = k; else: target = k+1. ans = sum(max(0, m_i - target) for i). Output ans.
But is sorting necessary? Since we need to assign the higher target to the largest r servers. Sorting O(n log n) with n up to 1e5 is fine. Could we avoid sorting by using partitioning? Possibly, but not needed.
But check boundary: n=1? Then S = m1. k = S, r = 0. n-r = 1. Target = k. Excess = max(0, m1 - k)=0. Answer=0. That's correct; no moves needed.
Edge cases: mi up to 20000, n up to 100k, sum up to 2e9, but within 32-bit signed? Actually 2e4 * 1e5 = 2e9, fits in 32-bit signed (max 2.147e9) but safe to use 64-bit (long long). Python's ints arbitrary, fine.
Now we must confirm the optimality of assigning +1 to the largest r servers. Let's double-check with cases where m_i may be exactly k+1, etc. Already covered. The delta_i analysis shows that the reduction in total absolute deviation from baseline (all k) when assigning +1 to a server is +1 if m_i >= k+1, -1 if m_i <= k. So to minimize sum_abs, we want to pick as many servers with m_i >= k+1 as possible. Since we must pick exactly r servers, if H >= r, pick r of those (preferably any r of them). If H < r, we must pick all H and then pick (r-H) servers from the low group, incurring penalty. That yields minimal sum_abs = C0 - (H1 + (r-H)(-1))? Actually if H < r, total reduction = H1 + (r-H)(-1) = 2H - r. So minimal sum_abs = C0 - (2H - r). The direct assignment of +1 to the largest r servers will achieve this because it will include all H high servers (since they are the largest) and then (r-H) from the low group which are the largest among low, but any low are fine. So indeed the direct assignment yields that sum_abs. So the answer formula works.
Now we need to implement in a programming language. The problem statement might be from Codeforces? Usually input reading. We'll just code accordingly.
But wait, there might be a nuance: The problem says: "In one second you can reassign a single task. Thus in one second you can choose any pair of servers and move a single task from one server to another." That's exactly moving 1 unit from one server to another. So each move reduces the surplus of one server and reduces the deficit of another. So indeed the minimal number of moves equals total surplus.
But is there any scenario where moving tasks indirectly might reduce moves? No, because each move directly transfers one unit, and the total surplus is the number of tasks that must be moved out of overloaded servers; each move can at most reduce surplus by 1, so at least total surplus moves are needed. And we can achieve exactly that by moving from each overloaded server directly to underloaded ones. So answer is total surplus.
Thus our solution is correct.
Now let's think about constraints: n up to 1e5, mi up to 2e4, sorting O(n log n) fine.
But we can also compute answer without sorting by counting how many servers are above or below target? Could we compute total surplus directly? Possibly using formulas. Let's explore: Let k, r. For each server i, if we assign target_i = k for all, then surplus_i = max(0, mi - k). But then total surplus S_surplus = sum max(0, mi - k). However, not all these surplus tasks need to be moved because we can increase the target of some servers to k+1, which reduces the required moves. Specifically, if we give a server +1, that server's required surplus reduces by 1 if it was above k+1? Actually careful: If a server has mi > k, it might be above k+1 or exactly at k+1. Let's compute the effect on total surplus when we change a server's target from k to k+1.
Define surplus_i(target) = max(0, mi - target). Initially with target = k, surplus_i = max(0, mi - k). After change to target = k+1, surplus_i' = max(0, mi - (k+1)). The difference delta_surplus = surplus_i' - surplus_i. Cases:
- If mi ≤ k: then surplus_i = 0, surplus_i' = 0 (since mi - (k+1) ≤ -1). So delta = 0? Actually wait: For mi ≤ k, mi - (k+1) is negative, so surplus_i' = 0. So delta = 0 - 0 = 0. But earlier we computed delta absolute deviations of -1. Here surplus is unchanged? But note that total moves = sum surplus. If we change a low server's target from k to k+1, its surplus stays 0, but its deficit increases by (k+1 - mi). That deficit must be compensated by surplus from other servers. However, total surplus must equal total deficit. So while surplus_i does not change (since it's not surplus), the deficit increases, meaning total surplus from other servers must increase to match. But wait, we are computing total surplus across all servers. The total surplus after assignment is sum_i max(0, mi - target_i). But the total deficit is sum_i max(0, target_i - mi). And they must be equal. So if we increase target of a low server, its surplus remains 0, but its deficit increases, so to maintain equality, total surplus from other servers must be at least as large. However, the target assignment also affects surplus of high servers when we change them. So we can't simply look at surplus differences individually; we need to consider the whole system. That's why we used absolute deviation approach. So direct computation of surplus using the sorted assignment is simpler.
Thus we'll implement sorting method.
But is sorting necessary? We could compute H = number of servers with mi > k (or >= k+1). Actually H = count of mi >= k+1. But also we need to know how many of the high servers are assigned +1. In the optimal assignment, all high servers get +1 if r >= H? Actually if r >= H, then all high servers get +1. If r < H, then only r of the high servers get +1. But we also need to know the sum of excess for the high servers that are not assigned +1? Because if a high server doesn't get +1, its target is k, so its surplus is mi - k. If it gets +1, its surplus is max(0, mi - (k+1)). So total surplus = sum_{i in high assigned +1} (mi - (k+1)) + sum_{i in high not assigned +1} (mi - k) + sum_{i in low} max(0, mi - k) but low have mi ≤ k so surplus 0. Also low assigned +1 have target k+1, but they have mi ≤ k, so surplus 0 as well. So total surplus = (for high servers) ... Actually, low servers never contribute surplus regardless of target because mi ≤ k, so even if target is k+1, mi - (k+1) is negative => 0 surplus. So surplus only comes from servers with mi > target. Those are servers with mi > k if target = k, or mi > k+1 if target = k+1. So only servers with mi > k can contribute surplus. Let's denote set A = {i: mi > k}. These are servers that have at least k+1 tasks. Among them, if we assign target = k, their surplus = mi - k; if we assign target = k+1, their surplus = mi - (k+1) if mi > k+1, else 0 (if mi = k+1, then surplus 0). So the total surplus is sum_{i in A} (mi - k) - number_of_servers_in_A_assigned_+1? Not exactly because for those with mi = k+1, if assigned +1, surplus becomes 0, which is a reduction of 1 from mi - k =1; if mi > k+1, assigned +1 reduces surplus by 1 as well. So each assignment of +1 to a server in A reduces its surplus by exactly 1, as long as mi >= k+1. For mi = k+1, reduction is 1 (from 1 to 0). For mi > k+1, reduction is 1 (from mi-k to mi-(k+1) = (mi-k)-1). So each +1 assigned to a server in A reduces total surplus by 1. If we assign +1 to a server not in A (i.e., mi ≤ k), it does not affect surplus (since surplus from that server remains 0). But it increases deficit, which means we must have more surplus from other servers. But that increase in required surplus is automatically accounted by the fact that total surplus must equal total deficit. However, the total surplus we compute as sum of positive deviations might not increase directly from assigning +1 to low servers; but the total moves (which is total surplus) will have to increase because we need to move tasks to satisfy the deficits. But wait, if we assign +1 to a low server, its target increases, so it will have deficit = target - mi. That deficit must be covered by surplus from other servers. However, the total surplus we compute as sum of positive deviations is exactly the tasks available to move. If we assign +1 to a low server, its own surplus does not change, but the total deficit increases by (k+1 - mi). To maintain balance, we need that the total surplus from other servers is at least that deficit. But if we don't increase surplus from others, the distribution is not feasible? Actually the total surplus is not predetermined; it is determined by the targets. When we assign targets, the sum of surpluses (positive deviations) must equal sum of deficits. So if we assign a low server a higher target, its deficit appears, which forces that the sum of surpluses from other servers must be at least that deficit. But the surpluses from other servers are determined by their own targets. So if we assign a low server +1, we are not directly changing the sum of surpluses; but the feasibility condition is that sum of all target_i equals S, which we enforce by having exactly r servers with +1. So the sum of deficits automatically equals sum of surpluses. So the total moves is the sum of surpluses, which is also half sum absolute deviations. So we can compute it as above.
Now, can we compute total surplus directly from counts and sums? Let's try to derive an expression. Let total sum S, n, k = floor(S/n), r = S%n. Let A be set of servers with mi > k. Within A, some are assigned target k, some k+1. The optimal assignment assigns +1 to as many as possible of A, specifically min(r, |A|) of them get +1, and the remaining +1's (if any) go to low servers. But note that assigning +1 to low servers doesn't affect surplus (since they don't generate surplus) but it creates deficit that must be met by surplus from A. So the total surplus after optimal assignment is: sum_{i in A} (mi - k) - (number of A that get +1). Because each +1 assigned to a server in A reduces its surplus by 1. For low servers, they don't contribute surplus. However, is the total surplus exactly that? Let's check with example where low servers get +1: earlier n=3, m=[0,0,2], k=0, r=2. A = servers with mi > 0: only the one with 2. sum_{i in A} (mi - k) = 2. Number of A assigned +1 = min(r,|A|) = min(2,1)=1. So computed total surplus = 2 - 1 = 1. That matches answer. Another: n=2, m=[1,6], k=3, r=1. A = servers with mi>3: only 6 (since 1 not >3). sum(mi - k) over A = 6-3=3. Number of A assigned +1 = min(1,1)=1. So surplus = 3-1=2. matches. Another: n=5, m=[1,2,3,4,5], k=3, r=0. A = servers with mi>3: 4 and 5. sum(mi - k)= (4-3)+(5-3)=1+2=3. Number of A assigned +1 = min(0,2)=0. Surplus=3. matches. Another: n=7 from example 2: k=10, r=4. A = servers with mi>10: those with 11. Count|A|=4? Actually m: three 10s, four 11s. So A = four servers with 11. sum(mi - k)=4*1=4. Number of A assigned +1 = min(4,4)=4. Surplus=4-4=0. matches. Another case: suppose n=4, m=[0,0,3,3], S=6, k=1 (6/4=1 floor 1), r=2 (6%4=2). A: servers with mi>1: both 3s => count=2. sum(mi - k)= (3-1)+(3-1)=4. Number of A assigned +1 = min(r,|A|)= min(2,2)=2. Surplus=4-2=2. Let's check manually: need two servers with target 2 (k+1) and two with target 1. Optimal to give +1 to the two 3s (since they are high). Then targets: 3->2, 3->2, 0->1, 0->1. Surplus: 3-2=1 each => total 2. Moves=2. Good.
What if r > |A|? Already considered. So formula: total surplus = sum_{i: mi > k} (mi - k) - min(r, |A|). Is that always correct? Let's derive formally.
Define:
- Let H = number of servers with mi > k (i.e., mi >= k+1). Actually ">" because if mi = k, then mi - k = 0 and not in A, but if mi = k, they are not >k. But what about mi = k exactly? They are not in A. For mi = k+1, they are >k, included. So A = {i | mi > k}.
- For each i in A, base surplus if target = k is mi - k. If we assign target = k+1, surplus reduces by 1 to (mi - (k+1)) = (mi - k) - 1. So each assignment of +1 to a server in A reduces total surplus by 1 compared to baseline (all k). For servers not in A, baseline surplus is 0 (since mi <= k). If we assign target = k+1 to such a server, its surplus remains 0, but its deficit becomes (k+1 - mi) > 0. However, the total surplus computed as sum positive deviations is unaffected by such assignments. But does the total surplus (the amount we need to move) equal the sum of positive deviations? Yes. And the total sum of positive deviations must equal total sum of deficits. If we assign +1 to a low server, we increase total deficit by (k+1 - mi), but we also need to have enough surplus to cover it. However, the sum of positive deviations is determined solely by the servers with mi > target. For low servers, they never contribute to positive deviations. So the sum of positive deviations is unaffected by assignments to low servers. So the total moves (which equals total positive deviations) depends only on how many +1 assignments are given to servers in A, not on assignments to low servers. But wait, is it possible that giving +1 to a low server could affect the total positive deviations? Could it cause some other server to have more surplus? No, because surplus from a server depends only on its own mi and target. So total positive deviations = sum over i in A of (mi - target_i) where target_i is either k or k+1. For i in A, target_i can be either, and for i not in A, target_i is either k or k+1 but since mi <= k, mi - target_i is <= 0, so contribution to positive is 0. So total positive deviations = sum_{i in A} (mi - target_i). Since mi - target_i = (mi - k) - (target_i - k). And target_i - k is either 0 or 1. So total = sum_{i in A} (mi - k) - sum_{i in A} (target_i - k). But note: target_i - k is 1 for those in A that are assigned +1, else 0. So sum_{i in A} (target_i - k) = number of A that are assigned +1. So total surplus = sum_{i in A} (mi - k) - X, where X = number of A servers assigned +1.
Now we have to assign exactly r servers to +1. Some of those may be from A, some from not A. Let X = number of +1 assignments to servers in A. Then total surplus = sum_A (mi - k) - X. The number of +1 assignments to not A is r - X. These do not affect total surplus directly. But we also need that the resulting distribution is feasible: the total deficit must equal total surplus. However, is there any constraint linking X? For feasibility, we need that total deficit = total surplus. Let's compute total deficit. Deficit arises from servers where target > mi. Those could be from A? For servers in A, if assigned target = k+1, could they have deficit? If mi = k+1 exactly and assigned +1, target = k+1, deficit 0. If mi > k+1, still no deficit because mi > target. So servers in A never have deficit. So deficit comes only from servers not in A (low servers) that are assigned +1 (since if assigned k, they are at or below target? Actually if low server with mi <= k, and assigned target = k, then if mi = k, deficit 0; if mi < k, deficit = k - mi? Wait careful: For low servers with mi <= k, if assigned target = k, then if mi < k, they have deficit (k - mi) > 0. Because target is k, they have fewer tasks than target, so they need tasks. So deficit can also arise from low servers assigned target k, not just those assigned +1. Hmm, this complicates. Our earlier assumption that low servers never contribute surplus but may contribute deficit regardless of target. Actually, for low servers (mi <= k), if assigned target = k, then deficit = k - mi (if mi < k). If assigned target = k+1, deficit = (k+1) - mi. So low servers always have deficit if mi < target. And target is either k or k+1. So they may have deficit in either case, unless mi equals the target exactly.
Thus our earlier simplification that total surplus equals sum_A (mi - target_i) is correct because positive deviations only from servers where mi > target. But total deficit = sum over all servers where target > mi of (target - mi). And that must equal total surplus. So when we set targets, we must ensure that the deficits can be covered by the surpluses. However, there is no additional constraint beyond the sum of targets equals S? Actually the sum of targets is n*k + r = S. The sum of mi is S. The sum of deviations (positive - negative) is zero, so automatically total surplus = total deficit. So any assignment of targets that respects the total sum will satisfy the balance condition. So we only need to ensure that the total sum of targets equals S. That is enforced by having exactly r servers with target k+1, rest k. So any such assignment yields a valid target distribution. However, the total surplus (and thus moves) can be computed as sum_{i: mi > target_i} (mi - target_i). And this depends on which servers get +1. Our earlier expression total surplus = sum_A (mi - k) - X is correct? Let's check: For servers not in A (mi <= k), they never contribute surplus because mi <= k <= target? Wait, if target = k and mi = k, surplus 0; if mi < k, then mi - k is negative, so surplus 0. If target = k+1, mi <= k < k+1, so mi - (k+1) negative => surplus 0. So yes, they never contribute surplus. So total surplus = sum_{i in A} (mi - target_i). And as derived, that equals sum_A (mi - k) - (number of A that got +1). So total surplus = S_A - X, where S_A = sum_{i: mi > k} (mi - k). So total surplus depends only on X, the number of +1 assignments given to high servers. However, we also have to consider that the deficits must be covered, but that is automatic if sum targets = S. But there might be a constraint that we cannot have X arbitrarily because we need to assign exactly r servers +1. So X can range from max(0, r - (n - |A|)) to min(r, |A|). Because we have n - |A| low servers. The number of +1 assignments to low servers is r - X. This must be ≤ n - |A| (since we can't assign +1 to more low servers than exist). So X ≥ r - (n - |A|). Also X ≤ min(r, |A|). So X is in that interval. Total surplus = S_A - X. To minimize total surplus (i.e., moves), we want to maximize X (since subtracting X). So the optimal X is the maximum possible, i.e., X_max = min(r, |A|). But also we need to ensure that X_max is ≥ the lower bound. Is it always? Because X_max = min(r, |A|). The lower bound is r - (n - |A|). Since n - |A| is number of low servers. r - (n - |A|) could be > min(r, |A|) if there are not enough low servers to cover the required +1 assignments when we give too many to high? Actually, if we give X = min(r, |A|), then low assignments = r - X. That must be ≤ n - |A|. Is r - min(r,|A|) ≤ n - |A|? Let's consider cases:
- If r ≤ |A|, then min = r, low assignments = 0 ≤ n - |A| (since n - |A| >=0). OK.
- If r > |A|, then min = |A|, low assignments = r - |A|. Need r - |A| ≤ n - |A| => r ≤ n. But r = S % n, so r < n, thus r ≤ n-1? Actually r can be up to n-1, but n - |A| is at least 0. Since r ≤ n-1, we have r - |A| ≤ (n-1) - |A|. But is it guaranteed that (n-1) - |A| ≤ n - |A|? Yes, trivially. However, we need r - |A| ≤ n - |A|, i.e., r ≤ n. Which holds because r < n (since remainder mod n is less than n). So yes, X_max is feasible. Thus optimal X = min(r, |A|). Therefore, minimal total surplus = S_A - min(r, |A|).
Now we must confirm S_A = sum_{i: mi > k} (mi - k). That is easy to compute without sorting if we can get that sum and count. But we also need to ensure that this total surplus equals the answer from the sorted assignment. Let's verify with some tests.
Test with n=3, m=[0,0,2], k=0, A = {2} (since >0), S_A = 2, min(r,|A|)=min(2,1)=1, surplus=1. Good.
Test with n=5, m=[1,2,3,4,5], k=3, A: servers with mi >3 are 4,5. S_A = (4-3)+(5-3)=3, min(r,|A|)=min(0,2)=0, surplus=3. Good.
Test with n=2, m=[1,6], k=3, A: {6}, S_A=3, min(1,1)=1, surplus=2. Good.
Test with n=7 example: k=10, A: servers >10 are those with 11, count=4, S_A = 4*1=4, min(r,|A|)=min(4,4)=4, surplus=0.
Test with a scenario where r > |A|: n=4, m=[0,0,1,1], S=2, k=0 (2/4=0 floor), r=2. A: servers >0? those with 1? Actually mi > 0 => 1, so two servers (indices 3 and 4). S_A = (1-0)+(1-0)=2. min(r,|A|)=min(2,2)=2, surplus=0. That suggests moves=0. But can we achieve load balanced? The ideal distribution: two servers with 1, two with 0. The initial: two servers have 1, two have 0. Already balanced? Check: max=1, min=0, difference=1, but minimal possible difference is 1 because r=2? Actually S=2, n=4, ideal distribution is exactly two 1's and two 0's. The initial is already exactly that? Let's see: m=[0,0,1,1]. That already has two 0's and two 1's. So max-min=1, which is minimal possible. So moves=0. Indeed our formula gives 0. Good.
What about scenario: n=4, m=[0,0,0,3], S=3, k=0 (floor 0), r=3 (since 3%4=3). A: server with 3 >0 => count=1, S_A=3-0=3. min(r,|A|)=min(3,1)=1, surplus=2. So answer=2. Let's manually think: Need three servers with 1, one with 0. Initial: 0,0,0,3. We need to get to e.g., 1,1,1,0. Surplus from 3: we need to move 2 tasks to three servers. That is 2 moves. Yes.
Thus formula minimal moves = sum_{i: mi > k} (mi - k) - min(r, count_of_servers_with_mi > k). That is O(n) without sorting! Because we just need to compute sum over mi > k of (mi - k) and count of such servers. But we must also ensure that this formula matches the sorted assignment and the delta analysis? Let's derive again.
Given k = floor(S/n), r = S%n. Let C = number of servers with mi > k. (Not >=, because mi = k does not count). Let excess_sum = sum_{i: mi > k} (mi - k). Then answer = excess_sum - min(r, C).
Is that always correct? Let's test more cases.
Case: n=5, m = [0,1,2,3,9]. S=15, k=3, r=0. C = servers >3: only 9 >3? Actually 3 is not >3, so just 9. So excess_sum = 9-3=6. min(r, C)=0, answer=6. But earlier we thought answer should be total surplus after all targets are k=3: targets: 3 each. Surplus from 9: 6, from others: none, so moves=6. That's correct.
Case: n=5, m = [0,1,2,4,8], S=15, k=3, r=0. C: >3: 4 and 8 => excess_sum = (4-3)+(8-3)=1+5=6, min(r,C)=0, answer=6. Let's verify: target all 3. Surplus: 4->1, 8->5 total 6, moves=6. Yes.
Case where some mi = k: they don't contribute.
Now consider r > 0. Example: n=5, m = [0,1,2,4,8], S=15? Actually sum=0+1+2+4+8=15, k=3, r=0. So not r>0. Let's adjust: n=5, m = [0,1,2,5,9], sum=17, k=3 (since 17/5=3.4 floor 3), r=2. C: >3: 5 and 9 => excess_sum = (5-3)+(9-3)=2+6=8. min(r,C)=min(2,2)=2, answer=6. Let's manually compute optimal: Need two servers with 4 (k+1), three with 3. Should give +1 to the high ones (5 and 9). Then targets: 5->4, 9->4, others 3. Surplus: from 5: 5-4=1; from 9: 9-4=5; total 6. Yes.
If we had r=3 in some scenario where C=2, then min(r,C)=2, answer=excess_sum - 2. For example, n=5, m = [0,1,2,5,9], sum=17? Actually that's 17, r=2. Let's make a different: m = [0,1,4,5,9], sum=19, k=3 (19/5=3.8 floor 3), r=4? 19%5=4. C: >3: 4,5,9 => C=3, excess_sum = (4-3)+(5-3)+(9-3)=1+2+6=9. min(r,C)=min(4,3)=3, answer=6. Let's verify: Need four servers with 4, one with 3. We have three high servers (>3) and two low (0,1). Optimal: assign +1 to all three high servers, and one low server gets +1 as well (since we need total 4). Then targets: high servers become 4, low server assigned +1 becomes 4 (say for 1), the other low (0) gets 3. Surplus: from high servers: 4->4? Actually 4-4=0, 5-4=1, 9-4=5 => total 6. Low server with 1 assigned +1: target 4, deficit 3; low server with 0 target 3 deficit 3; but surplus is only from high servers: 0+1+5=6. So moves=6. Our formula gives 6. Good.
Now consider case where some mi = k exactly and we might assign +1 to them. That would increase deficit but not surplus. Our formula using C = count(mi > k) doesn't include mi = k. But what about if a server with mi = k gets +1? That would create a deficit of 1, but we don't subtract from surplus because we don't reduce surplus from that server (since it had none). In the total surplus formula, we only subtract X (number of +1 assigned to servers in A). But what about +1 assigned to servers with mi = k? They are not in A, so they don't affect surplus. However, does that affect the feasibility of achieving the target distribution? Since total surplus must equal total deficit, if we create extra deficit, we need extra surplus. But if we keep X = min(r, C), we are maximizing X. The extra deficit from low servers is offset by the fact that we have less surplus (since we reduced surplus from high servers) but also we have to cover deficits of low servers. Wait, let's check the balance. Total deficit = sum_{i: mi < target_i} (target_i - mi). That will be comprised of deficits from low servers (both those assigned k and those assigned k+1). However, we need to ensure that total surplus computed as S_A - X equals total deficit. Let's derive total deficit in terms of known quantities.
Let L = set of servers with mi ≤ k. For these, if assigned target = k, deficit_i = k - mi (if mi < k). If assigned target = k+1, deficit_i = (k+1) - mi. Also there could be servers with mi = k exactly: if assigned target = k, deficit 0; if assigned target = k+1, deficit 1.
Now total sum of targets = S, sum of mi = S, so total surplus = total deficit. So the equality holds automatically. So we don't need to explicitly check.
Our formula answer = S_A - min(r, C). But is there any scenario where we might want to assign +1 to fewer high servers than max possible because assigning too many to high servers might create insufficient surplus to cover deficits? Actually, total surplus is S_A - X. The total deficit we can compute as sum of (target_i - mi) over all i where target_i > mi. Let's compute total deficit in terms of X and other parameters.
Define:
- n, total servers.
- Let count_H = C = |A| (mi > k). Let sum_H_excess = S_A = sum_{i in A} (mi - k).
- Let count_L = n - C (servers with mi ≤ k). For these, we can further split into those with mi = k and those with mi < k, but maybe not needed.
We assign +1 to exactly r servers. Let X = number of those +1 assigned to high servers (A). So r - X assigned to low servers (L).
Now compute total deficit.
First, consider high servers: They never have deficit because mi ≥ k+1? Actually if mi = k+1 and assigned target = k, then mi - k = 1 (surplus), not deficit. If assigned target = k+1, deficit 0. If mi > k+1, no deficit. So high servers have deficit 0 regardless.
Thus deficit only comes from low servers.
For low servers:
- Those assigned target = k: deficit_i = k - mi (if mi < k), else 0.
- Those assigned target = k+1: deficit_i = (k+1) - mi = (k - mi) + 1.
Let’s define for each low server its base deficit if target = k: d_i = k - mi (which is ≥ 0, since mi ≤ k). Then if assigned +1, deficit becomes d_i + 1.
Now, total deficit = sum_{i in L} d_i + (number of low servers assigned +1) because each +1 adds 1 to deficit. The number of low servers assigned +1 is r - X.
Thus total deficit = D + (r - X), where D = sum_{i in L} (k - mi). Note: D is total deficit if all low servers had target k (and all high servers had target k). But we have to also account that high servers might have target k or k+1, but that doesn't affect deficit. So total deficit = D + (r - X).
Now total surplus = S_A - X, as earlier.
Since total surplus must equal total deficit, we have S_A - X = D + (r - X) => S_A = D + r. So this equation must hold for consistency. Is it true? Let's verify. S = sum mi = sum_{i in A} mi + sum_{i in L} mi. Also note that S = nk + r. So sum_{i in A} mi + sum_{i in L} mi = nk + r. Rearranging: sum_{i in A} (mi - k) = (n*k - sum_{i in L} mi) + r? Actually let's derive:
Sum_{i in A} mi + sum_{i in L} mi = nk + r. => sum_{i in A} (mi - k) + |A|k + sum_{i in L} mi = nk + r. => S_A + |A|k + sum_{i in L} mi = nk + r. => S_A = nk + r - |A|*k - sum_{i in L} mi = (n - |A|)*k + r - sum_{i in L} mi = (|L|)*k + r - sum_{i in L} mi = sum_{i in L} (k - mi) + r = D + r.
Yes! So indeed S_A = D + r. This is an identity that holds always, given definitions. So the balance equation is automatically satisfied. Therefore, for any X, total surplus = S_A - X, total deficit = D + (r - X) = (S_A - r) + (r - X) = S_A - X. So indeed any assignment of X (subject to constraints) yields equal surplus and deficit. So no feasibility issue beyond the constraints on X. So we are free to choose X as large as possible to minimize surplus. Since surplus = S_A - X, maximizing X gives minimal surplus. So X_max = min(r, C) is feasible as argued. So answer = S_A - min(r, C). This formula is elegantly O(n) without sorting.
Thus we can solve in O(n) time.
But we must be careful: S_A = sum_{i: mi > k} (mi - k). And C = count of such i.
Let's test with more edge cases.
Case: n=1, m=[x]. S=x, k=x, r=0. mi > k? none, S_A=0, min(r,C)=0, answer=0. Good.
Case: all mi are equal to k or k+1? For example n=4, m=[2,2,2,2], S=8, k=2, r=0. C=0, S_A=0, answer=0. Good.
Case: all mi < k? Is that possible? Since k = floor(S/n), if all mi < k, then average would be less than k, contradiction because floor of average cannot be greater than all elements? Actually if all mi < floor(S/n), then sum < n * floor(S/n) ≤ S, but S = sum mi, so impossible. Similarly, all mi > k is impossible because sum would be > nk, but S = nk + r, so possible? Actually if all mi > k, then each mi ≥ k+1, sum ≥ n*(k+1) = nk + n > nk + r (since r < n), so sum would be too high. So there must be some low and high to balance. So our counts are fine.
Check case where some mi = k exactly. Those are not counted in A. Good.
Now is there any subtlety with mi exactly equal to k? For low servers, d_i = k - mi could be zero. If we assign +1 to such a server, deficit becomes 1. That is accounted in D + (r-X). The identity S_A = D + r holds because D includes zeros for those with mi=k.
Now test with a case where r = 0: answer = S_A - min(0, C) = S_A. That's sum of excess over k. That matches our earlier: need all target k, moves = total surplus.
Now test with a case where C = 0? That would mean all mi ≤ k. But if all ≤ k, then S_A = 0. Also S = sum mi ≤ nk, but S = nk + r. So r must be 0. Otherwise if r>0, sum would be nk + r > nk, contradicting all ≤ k. So if r>0, C cannot be 0. So safe.
Now test with r = n? r is remainder mod n, so r < n, so r can be at most n-1. So okay.
Now the answer is non-negative? Since S_A ≥ min(r, C) because each of the min(r,C) high servers we assign +1 reduces surplus by 1, but S_A is at least C? Actually S_A is sum of (mi - k) over A. Since each term is at least 1 (because mi > k), we have S_A ≥ C. Thus S_A - min(r, C) ≥ C - min(r, C) ≥ 0. If r ≤ C, then answer = S_A - r ≥ (C - r) ≥ 0? Actually S_A could be exactly C if all high servers have mi = k+1 exactly, then S_A = C, answer = C - r. If r > C, answer = S_A - C. Since S_A ≥ C, answer ≥ 0. Good.
Now we need to compute S_A and C. That's straightforward.
But we must also compute k = S // n. S up to 2e9, fits in 64-bit. But in Python fine.
Thus algorithm:
- Read n.
- Read list m of length n.
- Compute total = sum(m).
- k = total // n
- r = total % n
- Initialize excess_sum = 0, count_high = 0
- For each x in m: if x > k: excess_sum += (x - k) count_high += 1
- ans = excess_sum - min(r, count_high)
- Print ans
Double-check with given examples.
Example 1: n=2, m=[1,6]; total=7; k=3; r=1; excess_sum: 1>3? no; 6>3 yes -> 3; count_high=1; min(r,count_high)=1; ans=3-1=2. Good.
Example 2: n=7, m=[10,11,10,11,10,11,11]; total=74; k=10; r=4; excess_sum: count high: >10? 11>10 yes, each contributes 1, there are 4 such? Actually there are four 11s, yes, excess_sum=4; count_high=4; min(4,4)=4; ans=4-4=0. Good.
Example 3: n=5, m=[1,2,3,4,5]; total=15; k=3; r=0; excess_sum: 4>3 ->1, 5>3->2, total=3; count_high=2; min(0,2)=0; ans=3. Good.
Additional tests:
Test with n=3, m=[0,0,3] (sum=3, k=1? Actually 3/3=1, so k=1, r=0). excess_sum: >1? 3>1 ->2; count_high=1; min(0,1)=0; ans=2. But earlier we computed answer for this? Let's compute manually: target all 1. Surplus: 3-1=2, moves=2. Yes.
Test with n=3, m=[0,1,2] sum=3, k=1, r=0. excess_sum: >1? 2>1 ->1; count_high=1; ans=1. Manual: target all 1. Surplus: 2-1=1, moves=1. Yes.
Test with n=3, m=[0,0,2] sum=2, k=0, r=2. excess_sum: >0? 2>0 ->2; count_high=1; min(2,1)=1; ans=1. Good.
Test with n=3, m=[0,0,1] sum=1, k=0, r=1. excess_sum: >0? 1>0 ->1; count_high=1; min(1,1)=1; ans=0. Manual: Need one server with 1, two with 0. Already we have one with 1 and two with 0? Actually initial: 0,0,1 -> exactly that. So moves=0. Good.
Test with n=3, m=[0,2,2] sum=4, k=1 (4//3=1), r=1. excess_sum: >1? 2>1 ->1 each for two servers, total=2; count_high=2; min(1,2)=1; ans=1. Manual: Need one server with 2, two with 1? Because k=1, r=1 => one server with 2, two with 1. Initial: 0,2,2. Surplus: both 2's have surplus 1 each if target 1? But we can assign +1 to one of the 2's, then that server target 2, surplus 0; the other 2 target 1, surplus 1; the 0 target 1, deficit 1. Total surplus=1, moves=1. Good.
Test with n=3, m=[1,1,4] sum=6, k=2, r=0? 6/3=2, r=0. excess_sum: >2? 4>2 ->2; count_high=1; ans=2. Manual: all target 2, surplus from 4:2, moves=2. Good.
Now test a case where some mi = k exactly: n=4, m=[2,2,2,6], sum=12, k=3 (12/4=3), r=0. excess_sum: >3? 6>3 ->3; count_high=1; ans=3. But wait, is that correct? Targets all 3. Surplus: 6-3=3, others have deficit? 2<3, each deficit 1 (two 2's? Actually there are three 2's? m=[2,2,2,6] but we have three 2's? I wrote four numbers: [2,2,2,6] that's four numbers: three 2's and one 6. Sum=2+2+2+6=12, average 3. Target all 3. Surplus from 6=3; deficits: each 2 has deficit 1, total deficit 3. Moves=3. Good.
Now test where r>0 and some mi = k exactly: n=4, m=[2,2,2,5], sum=11, k=2 (11//4=2), r=3. excess_sum: >2? 5>2 ->3; count_high=1; min(r,C)=min(3,1)=1; ans=2. Manual: Need three servers with 3, one with 2. Initial: three 2's, one 5. Ideally, assign +1 to the 5 (so target 3) and to two of the 2's? Actually we need three servers with 3: so we must have three servers with target 3. One of them is the 5 (if we assign +1 to it, its target becomes 3). The other two 2's must also get +1 to become 3. So targets: 5->3, two 2's ->3, remaining one 2 ->2. Surplus: from 5: 5-3=2. Others have no surplus. Deficits: two 2's? Wait, the two 2's assigned +1 have deficit 1 each (since they need one task). The one 2 with target 2 has deficit 0. Total deficit = 2. Total surplus = 2, moves =2. Our answer 2. Good.
Now consider if we instead gave +1 to three 2's and not to the 5, then targets: 5 target 2, surplus 3; three 2's target 3, deficits 3; total surplus = 3, moves=3, worse. So optimal is to assign +1 to the high server.
Now what about scenario where there are multiple high servers and some have exactly k+1? That's included.
Thus formula seems solid.
Now we must confirm that answer is integer. Since excess_sum and min(r,C) are integers, answer is integer.
Now, could there be any scenario where we need to consider that moving tasks might require more moves because of indirect moves? The classic result is that the minimum number of unit transfers to achieve a target distribution is exactly the sum of positive differences (or total excess). Because each move can move one unit from a surplus to a deficit. So it's achievable.
Thus solution is straightforward.
Now let's think about corner case: n large, mi up to 20000, sum might be up to 2e9, but fine.
Time complexity: O(n). Space: O(1) extra beyond input.
Now we need to produce code: read input, compute as described.
But we need to ensure correctness: S_A = sum_{i: mi > k} (mi - k). However, is it possible that some servers have mi > k but we assign +1 to them, reducing their surplus by 1, but also some other servers with mi = k+1 that are not assigned +1 have surplus 1? In the optimal assignment, we assign +1 to as many high servers as possible, i.e., min(r, C). So we subtract exactly min(r, C) from S_A. But what about the case where a high server has mi = k+1, and we assign it +1, then its surplus becomes 0, effectively we subtract 1 from S_A. If we assign +1 to a high server with mi = k+100, we also subtract 1. So indeed each assignment of +1 to a high server reduces total surplus by 1, regardless of how high mi is. This seems plausible: For each such server, its contribution to surplus changes from (mi - k) to (mi - (k+1)) = (mi - k) - 1. So reduction of 1.
Now what about low servers that are assigned +1? They do not affect surplus. So indeed total surplus after optimal assignment = S_A - min(r, C). So answer computed.
Now we should verify with a random test using the sorted method to be sure. Let's do mental test: n=6, m = [0,3,3,3,3,6]. sum = 0+3+3+3+3+6 = 18. k = 18//6=3, r=0. excess_sum: >3? 6>3 ->3; also any 3 is not >3. So S_A=3, C=1, min(r,C)=0, answer=3. Sorted method: targets all 3. Surplus: from 6:3, moves=3. Good.
Now with r>0: change to m = [0,3,3,3,3,7] sum = 19, k=3 (19//6=3), r=1 (since 19%6=1). excess_sum: >3? 7>3 ->4; C=1; min(1,1)=1; answer=3. Sorted method: need one server with 4, five with 3. Sorted: [0,3,3,3,3,7]. n-r = 5. assign target=3 to first 5, target=4 to last. So targets: 0->3, three 3's->3? Actually first five: 0,3,3,3,3 get target 3; last 7 gets 4. Surplus: from 0? 0-3 negative =>0; from 3's: 0; from 7: 7-4=3. total 3. moves=3. Good.
Now case with multiple high servers and r less than C: n=5, m=[10,11,12,13,14] sum=60? Actually 10+11+12+13+14=60, k=12 (60/5=12), r=0. S_A: >12? 13>12 ->1, 14>12 ->2, total 3; C=2; answer=3. Sorted method: all target 12. surplus: 13-12=1, 14-12=2 =>3. Good.
Case r less than C but some high servers have exactly k+1: n=5, m=[10,10,11,11,12] sum=54? Let's compute: 10+10+11+11+12=54, k=10 (54/5=10 floor 10), r=4? 54%5=4. Actually 5*10=50, remainder 4. So k=10, r=4. m: >10? 11 and 12 are >10: 11,11,12. So C=3, S_A = (11-10)+(11-10)+(12-10)=1+1+2=4. min(r,C)=min(4,3)=3, answer=1. Sorted method: need four servers with 11, one with 10. Sorted: [10,10,11,11,12]. n-r=1, so first server (lowest) target 10, others target 11. Targets: 10->10, 10->11, 11->11, 11->11, 12->11. Surplus: from which? 10->10 surplus 0; 10->11 deficit; 11->11 surplus 0; 11->11 0; 12->11 surplus 1. total surplus=1. moves=1. Good.
Now test extreme: n=100000, all mi = 20000, sum=2e9, n=1e5, average = 20000, so k=20000, r=0. excess_sum = sum(mi - 20000) = 0. answer=0. Good.
Now test with random distribution: we could quickly write a small script to test but we trust.
Thus solution is simple.
Now we must write the program. Since input constraints up to 1e5, reading lines with Python is fine.
We need to output integer.
But we must consider integer overflow? Not in Python.
Now ensure the problem statement: "The second line contains the sequence of non-negative integers m1, m2, ..., mn (0 ≤ mi ≤ 2·104), where mi is the number of tasks assigned to the i-th server." So mi up to 20000.
Implementation steps:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) m = list(map(int, data[1:1+n])) total = sum(m) k = total // n r = total % n excess = 0 high_cnt = 0 for x in m: if x > k: excess += x - k high_cnt += 1 ans = excess - min(r, high_cnt) print(ans)
That's it.
Now, is there any scenario where the formula might not hold because moving tasks from a server with mi > k to a server with mi < k might need more moves due to intermediate steps? No, because we can always move directly.
Thus answer is correct.
But wait, what about the example in problem note? They gave: for third example (1 2 3 4 5) answer 3, matches.
Thus final answer.
Now just to be thorough, let's double-check the identity S_A = D + r. Because D = sum_{i: mi <= k} (k - mi). Then D + r = sum_{i: mi <= k} (k - mi) + r. But we also have S_A = sum_{i: mi > k} (mi - k). The sum of all mi = sum_{i > k} mi + sum_{i <= k} mi = nk + r. Rearranging gives sum_{i>k} mi - sum_{i>k} k = nk + r - sum_{i <= k} mi - sum_{i>k} k? Let's derive again:
S = sum_{i>k} mi + sum_{i<=k} mi = n*k + r.
Then sum_{i>k} mi = n*k + r - sum_{i<=k} mi.
Subtract sum_{i>k} k = C * k from both sides: sum_{i>k} (mi - k) = nk + r - sum_{i<=k} mi - Ck.
But nk - Ck = (n - C)*k = |L| * k.
So S_A = |L|*k + r - sum_{i<=k} mi = sum_{i in L} (k - mi) + r = D + r. Yes.
Thus identity holds.
Now note that D could be computed but we don't need it.
Now one might wonder: Could there be a scenario where we might want to assign +1 to a server with mi = k? Because that would increase deficit, but maybe that allows us to assign +1 to a high server with larger mi? But we already assign +1 to as many high servers as possible. The constraint is we must assign exactly r servers +1. If we assign +1 to a low server, that uses up one of the r slots, reducing the number we can assign to high servers. So to maximize X, we assign as many +1 to high servers as possible. That yields minimal surplus. So indeed no need to consider giving +1 to low servers beyond necessary.
Thus algorithm is correct.
Now let's confirm that the answer from the formula equals the number of moves described: In the third example, they moved tasks from servers with excess (4 and 5) to servers with deficit (1 and 2). Their sequence: first from 4 to 1, then from 5 to 1, then from 5 to 2. That's 3 moves. Our answer = 3. Good.
Now about the problem statement: It says "Print the minimum number of seconds required to balance the load." So we output the integer.
Now we should also consider if there is any possibility that we might need to move tasks not only from surplus to deficit but maybe via intermediate hops? But no.
Thus solution is done.
Now we will produce final answer with Python code.
But we need to be mindful of reading input: The input might have extra spaces, lines, but reading all tokens is fine.
Complexities: O(n) time, O(1) extra memory besides list.
Now I'll produce final answer. ```python
import sys
def main(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) m = list(map(int, data[1:1 + n]))
total = sum(m) k = total // n # floor of average r = total % n # number of servers that must get k+1 excess = 0 # sum_{mi > k} (mi - k) cnt_high = 0 # number of servers with mi > k for x in m: if x > k: excess += x - k cnt_high += 1 ans = excess - min(r, cnt_high) print(ans)if name == "main": main()