問題文
确实是 N 员工从左到右排成一排。 每个员工都有固定的身高,只有当他或她比他或她左边的所有员工都高时,从该行的左侧看时才能看到他或她的脸。
员工们已经排好了队,不过是左右挨着。 2 员工可以按任意顺序任意多次交换职位。 变换位置时,2 成本等于矮个子的身高。
总成本定义为每次更换的成本之和。
现在,当A先生从栏的左侧看时, N A先生希望他所有的员工都排队,以便他能看到他们的脸,只有当他们以实现这一目标的方式排队时,他才会感到满意。
您的任务是根据列中员工的身高,回答满足 A 要求的最低总成本。 然而,无论事情如何安排,A先生都可能不满意。在这种情况下,请报告。
入力
输入将以以下格式从标准输入给出。
N H_1 H_2 … H_N
- 1 行是一个整数,表示队列中的员工数量。 N (1≦N≦10^5) 给出。
- 2 行中显示该行中员工的身高。 N 整数由空格分隔。这几天之一 i(1≦i≦N) 从左侧开始 表示 i 位置员工身高的整数 H_i (1≦H_i≦10^8) 给出。
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- 1≦N≦1000 的数据集 如果您正确回答 1 , 如果您对30 点。 如果正确答案是满足
- 如果所有测试用例都回答正确,除上述之外, 在 70 点。 如果正确答案是满足
出力
1 行,输出 A 先生满意所需的最小总成本。但如果无论怎么安排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 。