← 返回题目列表

AtCoder · tkppc4_1_d

D. 跳过

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

配点 : 300 点

問題文

定义你们并排排列 我正在玩 N 方块。从左到右,正方形 它的编号为 1, 2, 3, ..., N 。
质量 从 i 是一个整数 写入A_i。玩法如下: 从

  • 质量 从 V_1 开始并跳过 M (M \geq 0) 位置广场 V_1, V_2, V_3, ..., V_M 以 V_M 结束。
  • 不能中途向左走。也就是说,1 \leq V_1 < V_2 < V_3 < ... < V_M \leq N 。
  • 此时的重点是|A_{V_2}-A_{V_1}| + |A_{V_3}-A_{V_2}| + ... + |A_{V_M}-A_{V_{M-1}}|成为一个点。
  • 您也可以选择不玩。在这种情况下 M = 0 重点是 0 点。另外,1 (M = 1 )也 0 点。

现在,define想要最大化点数,但他很懒,所以他想尽可能减少他经过的方格数量。
请计算给他通过的最少格数。

制約

  • 所有输入均为整数。
  • 1 \leq N \leq 10^5
  • -10^9 \leq A_i \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_{N-1} A_N

出力

为了最大化分数,确定您需要穿过的最小方格数。 1 行输出。


入力例1

5
1 2 1 2 1

出力例1

5

在这种情况下,如果您穿过所有方块,您将获得积分。 4 点。
你经过的方格 4 赚取以下积分 4 没有办法玩得比分数更多。


入力例2

5
1 3 5 2 1

出力例2

3

在这种情况下,质量 如果您按顺序浏览 1, 3, 5 您将获得 8 积分。

作者: 定义