#P0360. 加水

加水

题目描述

battle 有 nn 个水杯,每个水杯的容量都是 10001000

现在给出每个水杯中已有的水量,第 ii 个水杯中的水量为 aia_i。battle 想要给某些水杯加一些水(也可以不加),使得所有水杯的水量一致。

请问 battle 一共最少需要加多少水?

输入格式

第一行一个整数 nn

接下来一行 nn 个整数,a1ana_1\sim a_n

输出格式

一行一个整数,表示 battle 一共最少需要加的水量

4
3 1 1 4
7

样例解释

给四个水杯分别加上 1 3 3 01\ 3\ 3\ 0 单位的水即可。

数据规模与约定

对于 100%100\% 的数据,1n,ai10001\le n,a_i \le 1000

  • 子任务 1(30 分):对于 in1i\le n-1,保证 aiai+1a_i\ge a_{i+1}
  • 子任务 2(30 分):对于 in1i\le n-1,保证 aiai+1a_i\le a_{i+1}
  • 子任务 3(40 分):没有特殊限制。

有兴趣的同学可以想想不用数组能不能做。