1456:区域规划

时间限制: 2 S | 内存限制: 2048 KB
Accept: 19 | Submit: 67
[提交] [状态] [讨论版]
描述

在一个区域中有一排建筑,每个建筑都有一个影响力 x,我们规定,这个区域的综合实力等于该区域内影响力最高的建筑。有一天上级传达下来命令,需要把这个区域一分为二,同时使两个区域的综合实力之差尽可能大,请问这个差值可以达到多少。

输入

第一行是一个正整数 n 代表建筑物的数量。(2 <= n <= 4e5)

然后是 n 个小于等于 1e18 的正整数,分别代表这一排建筑从左到右影响力的大小。

输出

两个区域综合实力的最大差值,然后换行。

样例输入

4

3 4 6 5

样例输出

3

HINT

(3)  (4、6、5)  =>  abs(3 - 6) = 3

(3、4)  (6、5)  =>  abs(4 - 6) = 2

(3、4、6)  (5)  =>  abs(6 - 5) = 1

来源
TKK-ICPC Round#13