← 返回题目列表

AtCoder · awc0103_c

C. 展览布置

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

分数: 366 分

问题陈述

高桥负责美术馆的展览策划。对于即将到来的展览,他决定对作品进行策略性的安排,以便给参观者留下深刻的印象。

展会有 N 艺术品,每件编号为 1 to N。每件艺术品 i 有一个“音调值” A_i,它是艺术品色调亮度的数值表示。

高桥计划将艺术品单排展示。为了最大限度地提高对参观者的影响,他认为相邻艺术品之间的色调值差异越大,对比度就越突出,从而创造出更令人印象深刻的展览。

具体来说,当 N 艺术品排成一行,“影响值”定义为所有相邻艺术品对之间色调值绝对差的总和。也就是说,对于每个位置 1-st 到 (N-1)-th,计算该位置的图稿与下一个位置的图稿之间色调值的绝对差值,这些值的总和就是影响值。

看在高桥的份上,找到当艺术品排列成影响力值最大时的最大影响力值。

约束

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

输入

N
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 代表艺术品数量。
  • 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每件作品的色调值。

输出

在单行中输出最大影响值。


示例输入 1

4
1 3 8 10

示例输出 1

23

示例输入 2

5
7 7 7 7 7

示例输出 2

0

示例输入 3

10
12 45 3 89 34 21 76 55 8 100

示例输出 3

563

示例输入 4

30
42 1000000000 17 500000000 999999937 123456789 987654321 314159265 271828182 1 750000000 250000000 600000001 399999999 888888888 111111111 222222222 777777777 333333333 666666666 444444444 555555555 135791357 246802468 975318642 864209753 1024 2048 4096 8192

示例输出 4

18117750936

示例输入 5

1
1000000000

示例输出 5

0