3359. 这题真的是大水题

【问题描述】

众所周知,线段树是一个基础又好玩的数据结构,它可以实现非常的多的区间修改和查询问题,现在就有这么一个问题,可能需要你用可持久化线段树套平衡树二分01背包,题目是这样的,炮姐之前看到一道题,可持久化动态图上二维树状数组维护01背包,但是炮姐哪会啊,就拍了个线段树上去,wrong anwser on test 1。炮姐不想爆零,你能帮帮她吗? 
这道题是这样说的,给定一个含有n个 整数的序列a,保证数组中每一个元素的值都在INT_ MAX的范围内,现在你可以在任意位置上将序列分成两部分(保证均不为空),例如,序列a {1,2,3,4,5},你可以从1,2之间分,把序列变成{1}和{2,3,4,5}, 或者从2,3之间分, 把序列变成{1,2}和{3,4,5},设被分成两部分的序例分别为序列b和序列c,定义maxr(x)表示序列x中的最大值,定义minr(x)表示序列x中的最小值试求 
max {ans | ans= abs(maxr(bi)-maxr(ci)), i∈1,2,3,...,n-1 };  
min {ans | ans=abs(minr(bi)-minr(ci)), i∈1,2,3,...,n-1 }。 
其中bi,ci表示在i和i+1索引处将序例分开所表示的那一对序列,如{b1,c1}表示在序列a{1,2,3,4,5}的分成{1}和{2,3,4,5} 
如果对题面还有问题的话,请问群管理。 

【输入形式】

单组输入
第一行输入一个整数n,表示接下来有n个数。
接下来一行有n个数,保证所有数都在int范围内。
其中2<=n<=1e6。
注意序列中可以有负数。

【输出形式】

对于每组数据,输出两个整数,分别表示maxx和minn,中间用一个空格分开。

【样例输入】

5
1 2 35 9 11

【样例输出】

34 1

【样例说明】

样例解释:
对于最大值,我们选择在第一个和第二个数直接分开序列,也就是{b1,c1},序列b1为{1},序列c1为{2,35,9,11},maxx=abs(35-1)=34
对于最小值,我们选择在第一个和第二个数直接分开序列,minn=abs(2-1)=1

【评分标准】

难度等级: 0
总通过次数: 10
总提交次数: 28