← 返回题目列表

Codeforces · 484/D

D. 幼儿园

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

在幼儿园里,孩子们被分成小组。老师把孩子们排成一排,并将每个孩子与他或她的魅力值整数联系起来。每个孩子应该分到一组。每个组应该是一行的连续子项的非空段。一个群体的社交性是该群体中两个孩子的魅力的最大差异(特别是,如果该群体由一个孩子组成,则其社交性等于零)。

老师想把孩子们分成一定数量的小组,使小组的总社交性最大。帮助他找到这个价值。

输入

第一行包含整数 n — 该行中子级的数量 (1 ≤ n ≤ 106)。

第二行包含 n 个整数 ai - 第 i 个孩子的魅力 (- 109 ≤ ai ≤ 109)。

输出

打印所有群体的最大可能总社交能力。

示例

输入 #1

5
1 2 3 1 2

输出 #1

3

输入 #2

3
3 3 3

输出 #2

0

注意

在第一个测试样本中,划分的可能变体之一如下:前三个孩子形成社交能力为 2 的小组,其余两个孩子形成社交能力为 1 的小组。

在第二个测试样本中,任何划分都会导致相同的结果,每组中的社交性将等于 0。