分数: 800 点
问题陈述
我们有一个 煎饼塔 这是一堆 N 煎饼。最初, i从上往下数第一个煎饼 (1 \leq i \leq N) 的大小为 A_i。厨师高桥最多可以执行一次以下操作。
- 选择整数 l 和 r (1 \leq l \lt r \leq N) 并转动 l-th 通过 r第一个煎饼颠倒了,顺序颠倒了。
找到可能的最小值 丑陋 操作完成(或未完成)后塔的 ,定义如下:
丑是相邻煎饼大小差异之和;
即该值 |A^{\prime}_1 - A^{\prime}_2| + |A^{\prime}_2 - A^{\prime}_3| + \cdots + |A^{\prime}_{N-1} - A^{\prime}_N|,其中 A^{\prime}_i 是大小 i从顶部开始第一个煎饼。
约束
- 2 \leq N \leq 300000
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印塔的最小可能的丑陋。
示例输入 1
5 7 14 12 2 6
示例输出 1
17
如果我们进行选择操作 l = 2 和 r = 5,煎饼的尺寸为 7, 6, 2, 12, 14 从上到下。
这里的丑陋之处在于 |7-6| + |6-2| + |2-12| + |12-14| = 1 + 4 + 10 + 2 = 17。这是可能的最小值;没有办法减少丑陋。
示例输入 2
3 111 119 999
示例输出 2
888
在此示例中,不执行该操作可以最大限度地减少丑陋。
在这种情况下,煎饼的尺寸为 111, 119, 999 从上到下,为丑 |111-119| + |119-999| = 8 + 880 = 888.
示例输入 3
6 12 15 3 4 15 7
示例输出 3
19
如果我们进行选择操作 l = 3 和 r = 5,煎饼的尺寸为 12, 15, 15, 4, 3, 7 从上到下。
这里的丑陋之处在于 |12-15| + |15-15| + |15-4| + |4-3| + |3-7| = 3 + 0 + 11 + 1 + 4 = 19,这是可能的最小值。
示例输入 4
7 100 800 500 400 900 300 700
示例输出 4
1800
如果我们进行选择操作 l = 2 和 r = 4,煎饼的尺寸为 100, 400, 500, 800, 900, 300, 700 从上到下,为丑 1800.
示例输入 5
10 535907999 716568837 128214817 851750025 584243029 933841386 159109756 502477913 784673597 603329725
示例输出 5
2576376600