小蓝老师教的编程课有N 名学生, 编号依次是 1 … …N 。第 i 号学生这学期 刷题的数量是 � � A i ​ 。 对于每一名学生, 请你计算他至少还要再刷多少道题, 才能使得全班刷题 比他多的学生数不超过刷题比他少的学生数。

首先，我们可以将学生按照刷题数量从小到大排序，假设当前排完序后第 $i$ 名学生的刷题数量为 $a_i$。

考虑第 $i$ 名学生，如果他至少要再刷 $k$ 道题，才能满足题目要求，那么必须满足以下条件：

- 在前 $i-1$ 名学生中，刷题数量不超过 $a_i$ 的学生数量不超过 $\lfloor \frac{i-1}{2} \rfloor$，即刷题比他少的学生数量不超过 $\lfloor \frac{i-1}{2} \rfloor$；
- 在后 $N-i$ 名学生中，刷题数量不少于 $a_i+k$ 的学生数量不超过 $\lfloor \frac{N-i}{2} \rfloor$，即刷题比他多的学生数量不超过 $\lfloor \frac{N-i}{2} \rfloor$。

我们可以二分答案 $k$，判断是否满足上述条件。具体地，对于第一个条件，我们可以使用前缀和维护前缀中刷题数量不超过 $a_i$ 的学生数量。对于第二个条件，我们可以使用后缀和维护后缀中刷题数量不少于 $a_i+k$ 的学生数量。

时间复杂度为 $O(N \log N)$。