Alice 收到了一串包含 $n$ 个整数的序列作为生日礼物。由于她喜欢等差数列，她想把这份礼物变成一个等差数列。在等差数列中，相邻两项之间的差是一个常数。

她可以使用她的魔法对序列施法。她可以施展两种类型的法术。第一种是“增量咒语”：当她使用这个法术时，她可以选择序列中的一个数字并将其加一。另一种，正如你所猜到的，是“减量咒语”：她可以选择序列中的一个数字并将其减一。施展任一类型的法术都会消耗她 1 点法力值（Mana，魔法力量的单位）。

现在她想知道，为了使她的礼物成为等差数列，她最少需要消耗多少点法力值。Alice 不擅长数学，所以她向你寻求帮助。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示序列的长度。

第二行包含 $n$ 个整数 $a_i$ ($0 \le |a_i| \le 10^{13}$ 且 $1 \le i \le n$)，由空格分隔，表示初始序列。

输出格式

输出仅一个整数，表示她使序列成为等差数列所需消耗的最小法力值。

样例

输入 1

5
2 4 7 9 9

输出 1

3

说明

最优的方法是 $(2, 4, 7, 9, 9) \to (2, 4, 6, 9, 9) \to (2, 4, 6, 8, 9) \to (2, 4, 6, 8, 10)$，这共花费了 Alice 3 点法力值。