P4676. 守望塔对

场次：2026年3月28日-开发岗 · 来源：CodeFun2000 P4676

题目描述

你是一名通信工程师，正在部署一排线性的守望塔。共有 $n$ 座守望塔，从西到东依次编号为 $1$ 到 $n$。第 $i$ 座塔的高度记为 $h_i$。

对于两座塔 $i$ 和 $j$（$1 \le i < j \le n$），如果它们的高度之和大于它们之间所有塔（包括 $i$ 和 $j$）的最高高度，即满足

$h_i + h_j > \max_{i \le k \le j} h_k$

则称这一对塔可以互相通信。请统计所有可以互相通信的塔对 $(i, j)$ 的数量。

数据范围：塔的数量 $n$ 满足 $1 \le n \le 10^5$，每座塔的高度 $h_i$ 满足 $1 \le h_i \le 10^6$。

输入格式

第一行输入一个整数 $n$，表示塔的数量。 第二行输入 $n$ 个整数 $h_1, h_2, \dots, h_n$，依次表示每座塔的高度。

输出格式

输出一个整数，表示可以互相通信的塔对的数量。

示例

示例 1

输入：

1
5

输出：

0

说明：

当只有一座塔时，不存在编号 $i < j$ 的两座塔，因此无法形成任何塔对，答案为 0。

示例 2

输入：

2
1 2

输出：

1

说明：

唯一的一对是 $(1,2)$。$h_1 + h_2 = 1 + 2 = 3$，区间最大值为 $\max(1,2) = 2$。由于 $3 > 2$，该对满足条件，总数为 1。

示例 3

输入：

3
1 5 2

输出：

2

说明：

三座塔的可能对：

• 对 $(1,2)$：$1+5=6 > \max(1,5)=5$，满足。
• 对 $(2,3)$：$5+2=7 > \max(5,2)=5$，满足。
• 对 $(1,3)$：$1+2=3 \le \max(1,5,2)=5$，不满足。 所以共有 2 对满足条件。

示例 4

输入：

4
5 1 3 2

输出：

5

说明：

所有对的分析：

• $(1,2)$: $5+1=6 > \max(5,1)=5$，满足。
• $(1,3)$: $5+3=8 > \max(5,1,3)=5$，满足。
• $(1,4)$: $5+2=7 > \max(5,1,3,2)=5$，满足。
• $(2,3)$: $1+3=4 > \max(1,3)=3$，满足。
• $(2,4)$: $1+2=3 \le \max(1,3,2)=3$，不满足。
• $(3,4)$: $3+2=5 > \max(3,2)=3$，满足。 满足的对为除了 $(2,4)$ 以外的 5 对。