配点 : 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 积分。
作者: 定义