电梯经常拥挤不堪。有时你必须等待几分钟才能等到电梯，即使等到了，还要忍受所有从一楼乘电梯到二楼、三楼的人……直到你最终到达工作地点，可能已经过去了两个世纪。

考虑到这一点，几位在五楼工作的 Yandex 程序员决定改走楼梯。他们认为，这不仅能避开排队，还能锻炼身体。

他们太天真了，以为能避开排队。楼梯非常狭窄，你无法超越走在你前面且速度较慢的人。更糟糕的是，只有两条相同的楼梯通往五楼。这就是为什么走得快的人很快就会感到焦虑。

有 $n$ 个人在五楼工作。每天早上，他们按自然顺序（从第 1 个到第 $n$ 个）进入大楼。问题在于他们的速度不同。如果不受任何人干扰，第 $i$ 个人会在时间 $t_i$ 到达五楼。然而，如果有一个速度较慢的同事走在他前面的同一条楼梯上，第 $i$ 个人就必须减速，并且他到达的时间会与那个较慢的同事完全相同。

如果某人原本预计在时间 $x$ 到达工作地点，但实际上在时间 $y$ 才到达，他会说 $y - x$ 句脏话。程序员们足够聪明，意识到如果每个人都能明智地选择楼梯，那么总共说出的脏话数量就会减少。然而，他们无法找到最优的分配方案。请帮帮他们！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示程序员的人数。

第二行包含 $n$ 个整数 $t_1, \dots, t_n$ ($1 \le t_i \le 10^9$)，表示程序员按进入大楼的顺序排列的预期到达时间。

输出格式

输出所有人到达工作地点时，所说出的脏话总数的最小值。

样例

输入 1

5
100 4 3 2 1

输出 1

6

输入 2

6
5 1 6 2 7 3

输出 2

0

说明

在第一个样例中，最优方案是让速度最慢的第一个程序员走第一条楼梯，让其他人走第二条楼梯。在这种情况下，第三个程序员会说 1 句脏话，第四个程序员会说 2 句脏话，第五个程序员会说 3 句脏话。

在第二个样例中，最优方案是让第 1、3、5 个程序员走第一条楼梯，让其余程序员走第二条楼梯。