题目思路

最优的操作其实就是让小于它的数一直自增直到其等于指定元素，大于它的数一直自减直到其等于指定元素。

所以对每个元素我们需要找到大于它的元素数量和元素之和，小于它的元素数量和元素之和就可以计算出答案。

可以增加一个排序后的镜像的数组，对每个元素找到其在排序后的镜像数组的下标位置,这个可以通过二分找到，也就找到了小于它的元素数量和大于它的元素数量。元素之和则考虑使用前缀和优化即可。

代码

题目描述

小红拿到了一个数组，他每次操作可以任选一个元素加1或者减1。他想知道，将所有元素都变成和$a_i$相等需要操作最少多少次?你需要回答$i ∈[1,n]$的结果，

输入描述

第一行输入一个正整数$n$，代表数组的大小。

第二行输入$n$个正整数$a_i$。

$1\le n \le 10^5$

$1\le a_i \le 10^9$

输出描述

输出$n$行，代表每一个$i$对应的结果。

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3
2 1 4

输出

3
4
5