问题说明

Indeed 公司有 N 名员工，他们从左到右排成一列。每个员工都有确定的身高，只有当他的身高高于他左边所有员工的身高时，我们才能从左侧看到他的脸。

员工们已经排好队了，相邻的两个员工可以自由交换位置，并且可以无限次地进行交换操作。交换位置时，需要花费较低身高的员工身高之差作为代价。

总代价定义为所有交换操作的代价之和。

现在，A先生希望员工从左侧看到所有 N 名员工以满足他的要求，并且只有在达到这个要求时，A先生才会感到满意。

你的任务是根据给定的员工身高，确定满足 A 先生要求所需的最小总代价。但是，无论如何排列，A 先生可能不满意，请在这种情况下报告。

输入

输入通过标准输入给出，格式如下：

N H1 H2 ... HN

• 第 1 行是一个整数 N (1≦N≦10^5)，表示员工的数量。
• 第 2 行是 N 个整数，用空格分隔，表示排队的员工的身高。其中第 i(1≦i≦N) 个数字表示排在第 i 个位置的员工的身高，整数 Hi (1≦Hi≦10^8)。

部分分

此问题设置了部分分。

• 对于满足 $1≦N≦1000$ 的数据集 1 给出正确答案，可获得 30 分。
• 对所有测试用例给出正确答案，除上述分数外还可获得额外的 70 分。

输出

输出最小总代价，满足 A 先生要求时，输出 -1。输出的末尾应包含换行符。

示例

输入示例1

4
4 1 3 2

输出示例1

8

按照从左到右的顺序排列身高为 $1,2,3,4$ 的员工，这样从左边看，可以看到每个员工的脸，A 先生会满意。

达到这个要求的最小总代价是 8，可以通过以下交换来实现：

• 首先，将身高为 4 的员工和身高为 1 的员工交换位置。此操作的代价为 1，交换后的顺序为 $1,4,3,2$。
• 然后，将身高为 4 的员工和身高为 3 的员工交换位置。此操作的代价为 3，交换后的顺序为 $1,3,4,2$。
• 接着，将身高为 4 的员工和身高为 2 的员工交换位置。此操作的代价为 2，交换后的顺序为 $1,3,2,4$。
• 最后，将身高为 3 的员工和身高为 2 的员工交换位置。此操作的代价为 2，交换后的顺序为 $1,2,3,4$。

输入示例2

5
1 1 2 2 3

输出示例2

-1

无论如何排列，我们都不能同时看到相同身高的人的脸。因此，应输出 -1。