题目内容

某仓储公司在一条笔直通道上依次排列了 $n$ 个仓库，第 $i$ 个仓库的库存量为整数 $a_i$。公司需要将这些仓库划分为若干非空连续区段，且所有区段按原顺序首尾相接覆盖全部仓库。对于区段 $[L,R]$，其长度为 $R-L+1$，收益定义为该区段内库存量最大值与最小值之差乘以区段长度：

求所有区段收益之和可以达到的最大值。

限制：$1 \le n \le 3 \times 10^5$，$1 \le a_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示仓库数量。 第二行包含 $n$ 个用空格分隔的整数 $a_1,a_2,\dots,a_n$，表示从左到右每个仓库的库存量。

输出描述

输出一个整数，表示最优划分下所有区段收益之和的最大值。

样例1

输入

1
7

输出

0

说明

只有 1 个仓库，无论怎么划分都只能是整段。区间 $[1,1]$ 的最大值和最小值都等于 $7$，差值 $M-m=0$。

因此收益为 $(M-m)\times n=0\times 1=0$。

样例2

输入

4
5 2 9 1

输出

32

说明

全局最大值 $M=9$，全局最小值 $m=1$，差值 $M-m=8$。

若把整段作为唯一区段，收益为 $(M-m)\times n=8\times 4=32$。任意划分中，每个区段的极差都不超过 $8$，所有区段长度之和恒为 4，因此总收益不可能超过 32。

样例3

输入

5
10 20 10 20 10

输出

50

说明

最大值和最小值分别为 $20$ 和 $10$，差值为 $10$。

整段不切割时收益为 $(20-10)\times 5=50$。即使某些区段极差变小，所有区段长度之和仍为 5，且每段极差上界为 $10$，所以总贡献无法超过 50。

样例4

输入

3
1000000000 1 1000000000

输出

2999999997

说明

全局最大值为 $1000000000$，最小值为 $1$，差值为 $999999999$。

整段收益为 $(1000000000-1)\times 3=999999999\times 3=2999999997$。该结果超过 $32$ 位有符号整数范围，因此需要用 $64$ 位整数保存。