题目描述

给你一个长度为 $n(1 \le n \le 10^6)$ 的整数数列 $a_1, a_2, \cdots, a_n(-10^9 \le a_i \le 10^9)$。你需要给这个数列分成若干段连续子序列，使得这些连续子序列的价值之和最大。

我们定义一个连续子序列的价值为：这个子序列中最大的数与最小的数之差。

输入格式

第一行包含一个整数 $n$，表示数列的长度（$1 \le n \le 10^6$）。
第二行包含 $n$ 个整数，其中第 $i$ 个整数表示数列中的第 $i$ 个元素 $a_i(-10^9 \le a_i \le 10^9)$，相邻两数之间以一个空格分隔。

输出格式

一个整数，表示所有划分方案中，子序列价值之和的最大值。

样例

5
1 2 3 1 2

3

3
3 3 3

0

数据范围

对于 $100\%$ 的数据：$1 \le n \le 10^6, -10^9 \le a_i \le 10^9$。