← 返回题目列表

AtCoder · past202306_k

K. 交换和排序

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

问题陈述

有一个长度为 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

有时,不需要任何操作。