← 返回题目列表

AtCoder · indeednow_2015_finalb_e

E. 排队!

中文机器翻译题面 查看原题

問題文

确实是 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 。