← 返回题目列表

AtCoder · arc119_e

E. 煎饼

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

分数: 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