配点: 6 点
問題文
长度 小于或等于 2N 的正整数序列 给出了 A=(A_1,A_2,\ldots,A_{2N}) 。 具有以下操作的列 考虑从 A 中删除一个数字。
- 剩余列 满足 (A^{\prime}_1,A^{\prime}_2,\ldots,A^{\prime}_M) 。 1\leq i<M 的整数 选择 i ,A^{\prime}_i 和 按字典顺序比较 A^{\prime}_{i+1} 。执行此操作后,剩余的列是 (A^{\prime}_1,\ldots,A^{\prime}_{i-1},A^{\prime}_{i+2},\ldots,A^{\prime}_M) 。
此操作需要 成本 需要 。 1 操作的成本是删除的数量。 A^{\prime}_i,A^{\prime}_{i+1} 作为 |A^{\prime}_i-A^{\prime}_{i+1}| 。
此操作 执行 N 次 当从 A 中删除所有数字时, 求N 操作的最小可能总成本。
制約
- 1 \leq N \leq 200
- 1 \leq A_i \leq 10^6\ (1\leq i\leq 2N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
A_1 A_2 \ldots A_{2N}
出力
N 请输出运营总成本的最小可能值。
入力例 1
3 6 2 3 9 8 6
出力例 1
2
下面显示了最小化总成本的操作示例。 执行该操作的成本为
- i=2 和|2 - 3| = 1 。该行是 (6,9,8,6) 变为。
- i=2 和|9 - 8| = 1 。该行是 (6,6) 变为。
- i=1 和|6 - 6| = 0 。该行是 () 变为。
3 总运营成本为 2 。 对于
入力例 2
3 1 3 5 5 3 1
出力例 2
0
入力例 3
4 1 2 4 8 16 32 64 128
出力例 3
85
入力例 4
15 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
出力例 4
207