242051 - 近似均等化

题目描述

给定一个整数序列 A=(A_1,A_2,\ldots,A_N)。你可以执行任意多次(也可以不执行)以下操作:选择两个整数 i 和 j(1 \le i,j \le N),将 A_i 减 1,并将 A_j 加 1。求使得序列 A 中的最大值与最小值的差不超过 1 所需的最少操作次数。

输入

第一行一个整数 N。
第二行 N 个整数 A_1,A_2,\ldots,A_N。

输出

输出一个整数 ans,表示所需的最少操作次数。

样例

输入

4
4 7 3 7

输出

3

输入

1
13

输出

0

输入

10
97 99 4 3 2 4 90 8 91 93

输出

224
说明

【数据范围】
1 \le N \le 2 \cdot 10^5; 1 \le A_i \le 10^9;
所有输入值均为整数;
输出答案 ans 满足 0 \le ans \le 2 \cdot 10^{14}。
【样例说明】 样例 1 中,通过以下三次操作可以使序列 A 的最大值与最小值之差不超过 1:选择 i=2 和 j=3,A 变为 (4,6,4,7)。选择 i=4 和 j=1,A 变为 (5,6,4,6)。选择 i=4 和 j=3,A 变为 (5,6,5,5)。无法在少于三次操作内使最大值与最小值之差不超过 1,因此答案为 3。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 1 枚
难度 入门


上一题 下一题