Given $A_1,A_2,\cdots ,A_n$, please count the number of valid pairs of ($l,r$) where $l\le r$ and $A_l+A_r=ma{x}_{i=l}^r{A}_i$.

Input format:

The first line contains a single integer n(1≤n≤500000).

The second line contains n integers, indicating A1,A2,⋯,An(0≤Ai≤109,1≤i≤n).

Output format:

Output a single integer, indicating the number of valid (l,r) pairs.

Example input:

6
1 3 2 5 7 4

Example output:

2

以索引为k，以值为val，建立一棵笛卡尔树，以便于在O(1)时间复杂度内获取每一个节点支配的范围

运用启发式合并的思想，选取左右两边较少的一侧进行尝试，利用map快速获取另一侧中符合条件的节点数

问题：因为笛卡尔树是堆与二叉搜索树的结合，所以对于重复元素插入会存在一些问题

分析：根据插入操作的运行逻辑，当重复插入时，有下列三条规律一定成立：

1）重复的元素可能会被分配到一个节点的两棵子树中

2）同一棵子树中的重复元素一定是相邻的（在同一条右链上）

3）每个重复元素的左子树仍然满足“子树中所有元素均小于根节点”的条件

考虑到0的存在，所以重复元素应该被划入支配范围内

解决问题：我们分类讨论相邻和不相邻两种情况：

1）对于相邻元素，我们直接找到最上层的那个节点，然后以此计算支配范围

2）如果不在一棵子树中，是没必要考虑的，因为当我们把不在一棵子树中的重复元素划入同一区间，这个区间的最大值必然发生改变

#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int max_n = 500000;typedef struct {int val, l, r;
}node;int n;
node tr[max_n + 1];
int rsp = 0, stk[max_n + 1];
int rt, sz[max_n + 1], fa[max_n + 1];
map<int, vector<int>>loc;inline int read() {int x = 0; char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}int dfs(int cur) {if (cur == 0) return 0;sz[cur] = 1;sz[cur] += dfs(tr[cur].l);sz[cur] += dfs(tr[cur].r);
}void build_tree() {int k = 0;for (int i = 1; i <= n; i++) {fa[i] = i;k = rsp;while (k > 0 && tr[stk[k]].val < tr[i].val) k--;if (k) {if (tr[stk[k]].val == tr[i].val) fa[i] = fa[stk[k]];tr[stk[k]].r = i;}if (k < rsp) tr[i].l = stk[k + 1];stk[k + 1] = i;rsp = k + 1;}rt = stk[1];dfs(rt);
}int query(int val, int idx) {idx = fa[idx];int lsz = sz[tr[idx].l], rsz = sz[tr[idx].r];int l = idx - lsz, r = idx + rsz;int ret = 0;if (lsz < rsz) {for (int i = l; i <= idx; i++) {if (!loc.count(val - tr[i].val)) continue;for (auto iter : loc[val - tr[i].val]) {if (iter >= idx && iter <= r) ret++;}}}else {for (int i = idx; i <= r; i++) {if (!loc.count(val - tr[i].val)) continue;for (auto iter : loc[val - tr[i].val]) {if (iter >= l && iter <= idx) ret++;}}}return ret;
}int main() {n = read();for (int i = 1; i <= n; i++) {tr[i].val = read();if (loc.count(tr[i].val)) loc[tr[i].val].push_back(i);else {vector<int>tmpv;tmpv.push_back(i);loc[tr[i].val] = tmpv;}}build_tree();int ans = 0;for (int i = 1; i <= n; i++) ans += query(tr[i].val, i);printf("%d", ans);return 0;
}