这里有一种分治的做法。
考虑当前分治区间[L,R]，区间中心为mid，我们需要解决的问题是求出所有跨越mid的区间的答案。
首先枚举右端点r(左端点也是一样的，这里只是举个栗子)，对于所有左端点l和最大值(最小值)，可能的情况有三种：
1、max(l,mid)>max(mid,r)
2、max(l,mid)=max(mid,r)
3、max(l,mid)<max(mid,r)
可以发现，这三种情况是分别连续的，且随着r的变化，这三种情况的分界点的变化也是单调的。
最小值同理。
根据这个性质就可以在O(n)的时间里求出所有跨越mid的区间的答案。
结合分治，就把问题解决了。
总复杂度O(nlogn)