解题思路
设区间为 [l,r]，题目要求满足：
l<r,vl+vr>k=lmaxrvk
直接枚举区间显然是 O(n2)，无法通过 n≤105 的数据范围，必须使用更高效的算法。
P4672.第4题-小美的区间
题目内容
小美喜欢研究整数序列在区间上的性质。
她手中有一个长度为 n 的序列 v1,v2,…,vn。
他想统计序列中有多少个区间长度大于 1 的区间满足区间最大值小于区间左右端点值之和。即有多少区间[i,j]（1≤i<j≤n）满足：
vi+vj>maxk=ijvk
输入描述
第一行输入一个整数 n（1≤n≤105），表示序列长度。
第二行输入 n 个整数v1,v2,…,vn（1≤vi≤106），表示序列元素。
输出描述
输出满足区间长度大于 1 且vi+vj>maxk=ijvk 的区间 [i,j] 的数量。
示例 1
输入
5
1 2 3 4 5
输出
10
说明
序列为{1,2,3,4,5}。
- 任意长度大于 1 的区间 [i,j]，最大值均为 vj。
- 因此 vi+vj>vj恒成立，共有 10 个区间满足条件。
