题目描述

给定一个大小为 $n(2 \le n \le 1000)$ 的数列 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^5)$。

你可以对这个数列进行任意次操作，每次操作，你可以：

选择任意一个下标 $i(2 \le i \le n)$，将 $a_i$ 减小 $1$，同时将 $a_1$ 增加 $1$。

你的目标是让 $a_1$ 比数列中的其它元素都大，即最终对于任意下标 $2 \le i \le n$ 均有 $a_1 \gt a_i$。

求：最少操作次数。

输入格式

第一行，一个整数 $n(2 \le n \le 1000)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^5)$，两两之间以一个空格分隔。

输出格式

输出一个整数，表示令 $a_1$ 最大的最少操作次数。

input1

5
5 1 11 2 8

output1

4

input2

4
1 8 8 8

output2

6

input3

2
7 6

output3

0

说明/提示

样例解释

• 样例1中，一种最优方案是：选择将 $a_3$ 减 $4$ 次 $1$，数列变成 $[9,1,7,2,8]$
• 样例2中，一种最优方案是：选择将 $a_2,a_3,a_4$ 各减去 $2$ 次 $1$，数列变为 $[7,6,6,6]$
• 样例3中，不需要进行任何操作，$a_1$ 本身就是最大的

数据规模与约定

• 对于 $40\%$ 的数据，$n \le 10, a_i \le 100$
• 对于 $80\%$ 的数据，$n \le 100, a_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 1000, 1 \le a_i \le 10^5$