问题陈述
有一个长度为 N, P=(P_1,P_2,\ldots,P_N),这是一个排列 (1,2,\ldots,N).
您可以对此序列执行以下操作任意次数,可能为零:
- 选择一个整数 i 之间 1 和 N-1,包含在内,并交换 i第一个元素和 (i+1)- 第一个元素 P。此操作的成本是被交换的两个数字的总和。
求排序所需的最低成本 P 按升序排列。
约束
- 1 \leq N \leq 2\times 10^5
- N 是一个整数。
- P 是一个排列 (1,2,\ldots,N).
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N
输出
打印答案。
样本输入 1
4 3 2 1 4
示例输出 1
12
例如,您可以排序 通过执行以下三个操作按升序排列 P :
- 选择 i=1 交换 3 和 2。 5,序列变为 (2,3,1,4).
- 选择 i=2 交换 3 和 1。 4,序列变为 (2,1,3,4).
- 选择 i=1 交换 2 和 1。 3,序列变为 (1,2,3,4).
由于不可能以小于 12,答案是 12.
示例输入 2
9 3 1 4 5 9 2 6 8 7
示例输出 2
96
示例输入 3
6 1 2 3 4 5 6
示例输出 3
0
有时,不需要任何操作。