logo AlgoBeat OnlineJudge
登录 注册

#1046. [Algo Beat Contest 006 I] 出征

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: sonny2011 管理员

题目描述

yuchangzhu 的军队准备出征。军队包含 个人,按顺序站成一排,第 个人有一个体力值 。yuchangzhu 要对这些人任意多次以下操作:

  • 选择一个正整数 ,满足
  • 对于每一个 ,满足 ,可以选择使第 个人的体力增大或减小(所有人同时增大减小,即都选增大或者都选减小) 。在这里, 是组合数,即 指的是从 个物品中选择 个的方案数(选择的顺序不重要)。

yuchangzhu 想让所有人的体力值较为均等。请问至少进行几次操作,可以使所有人的体力值都变为

输入格式

第一行,包含三个整数 ,含义如题目描述。

第二行,包含 个整数,表示每人的体力值。

输出格式

一个整数,表示答案。

样例

输入输出样例 #1

输入 #1

4 1 0
2 2 2 2

输出 #1

1

数据范围与提示

【数据范围】

对于 的数据,保证

另有 的数据,保证

对于 的数据,保证