该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小S非常喜欢玩。最重要的是，他喜欢玩下面的游戏：

给他一连串的 N 个整数的序列。在每一步，允许任何数字的值增加1 ，或减少1 。游戏的目标是以最小的步数使序列不递减。小S不擅长数学，所以他请求你的帮助。

该序列 a 被称为非递减，如果 a₁ ≤ a₂ ≤ ... ≤ a_N成立，其中 N 是序列的长度。

输入

输入的第一行包含单个整数 N(1 ≤ N ≤ 5000)--初始序列的长度。接下来的 N 行各包含一个整数--序列的元素。这些数字不超过 10⁹的绝对值。

输出

输出一个整数--实现目标所需的最小步骤数。

Samples

5
3 2 -1 2 11

4

5
2 1 1 1 1

1