题目内容

在一排直线上竖立着 $n$ 座通信塔，从左到右编号为 $1$ 到 $n$，第 $i$ 座塔的高度为 $h_i$。对于任意一对塔 $i$ 和 $j$（$i<j$），若区间 $[i,j]$ 内最高的塔的高度严格小于两座塔的高度之和，即 $h_i + h_j > \max_{i \le k \le j} h_k$，则这对塔可以建立一条通信链路。请你统计所有可以建立通信链路的配对数量。

数据范围：$1 \le n \le 10^5$，$1 \le h_i \le 10^6$。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示塔的数量。 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^6$)，依次表示每座塔的高度。

输出描述

输出一个整数，表示满足条件的配对 $(i,j)$ 的数量。

样例1

输入

1
7

输出

0

说明

只有一座塔，不存在满足 $i < j$ 的配对，因此答案为 0。

样例2

输入

3
2 5 2

输出

2

说明

配对情况如下：

• $(1,2)$：区间 $[1,2]$ 内最高塔高度为 $5$，$2+5=7>5$，满足条件。
• $(2,3)$：同理 $5+2=7>5$，满足条件。
• $(1,3)$：区间 $[1,3]$ 最高塔高度为 $5$，而 $2+2=4<5$，不满足条件。 因此共有 2 对。

样例3

输入

5
2 1 10 1 2

输出

6

说明

共有 6 对满足 $h_i + h_j > \max_{i \le k \le j} h_k$：

• $(1,2)$：$2+1=3 > \max(2,1)=2$。
• $(1,3)$：$2+10=12 > \max(2,1,10)=10$。
• $(2,3)$：$1+10=11 > 10$。
• $(3,4)$：$10+1=11 > 10$。
• $(3,5)$：$10+2=12 > \max(10,1,2)=10$。
• $(4,5)$：$1+2=3 > \max(1,2)=2$。 其余如 $(1,4)$、$(1,5)$、$(2,4)$、$(2,5)$ 等均因为区间最高塔 $10$ 过大导致两侧塔高之和不足而无法通信。