解题思路

设区间为 $[l,r]$，题目要求满足：

直接枚举区间显然是 $O(n^2)$，无法通过 $n\le 10^5$ 的数据范围，必须使用更高效的算法。

题目内容

小美喜欢研究整数序列在区间上的性质。

她手中有一个长度为 $n$ 的序列 $v_1,v_2,\ldots,v_n$​。

他想统计序列中有多少个区间长度大于 1 的区间满足区间最大值小于区间左右端点值之和。即有多少区间$[i,j]$（$1\le i<j\le n$）满足：

$v_i+v_j>\max_{k=i}^{j} v_k$

输入描述

第一行输入一个整数 $n$（$1\le n\le 10^5$），表示序列长度。

第二行输入 $n$ 个整数$v_1,v_2,\ldots,v_n$（$1\le v_i\le 10^6$），表示序列元素。

输出描述

输出满足区间长度大于 $1$ 且$v_i+v_j>\max_{k=i}^{j}v_k$ 的区间 $[i,j]$ 的数量。

示例 1

输入

5
1 2 3 4 5

输出

10

说明

序列为$\{1,2,3,4,5\}$。

• 任意长度大于 1 的区间 $[i,j]$，最大值均为 $v_j$。
• 因此 $v_i + v_j > v_j$恒成立，共有 $10$ 个区间满足条件。