小田的山峰数组

mountain.in mountain.out

题目描述

一个山峰数组定义为由三个元素组成的 $[a_{1}, a_{2}, a_{3}]$，满足 $a_{1}<a_{2}$ 且 $a_{2}>a_{3}$ 。

现在小田有一个长度为 $n$ 的数组 $P$，他将选择两个下标 $i, j(1 \le i < j \lt n)$，然后以此为基准将数组分成三个非空连续的子数组，即 $[P_{1}, ..., P_{i}]$，$[P_{i+1}, ..., P_{j}]$，$[P_{j+1}, ..., P_{n}]$ 。

假设 $b_{1}, b_{2}, b_{3}$ 分别是这三个子数组的元素之和，小田希望 $[b_{1}, b_{2}, b_{3}]$ 是一个山峰数组。

现在小田想知道一共由多少个不同的 $(i, j)$ 可以满足他的要求，请你帮他计算一下。

输入描述

第一行一个正整数 $n$，表示数组 $P$ 的长度。

第二行输入 $n$ 个整数 $P_i$，表示第 $i$ 个元素的值。

输出描述

输出一个整数，表示可以得到的山峰组数个数。

输入输出样例

输入 #1

5
1 2 3 4 5

输出 #1

2

输入 #2

4
3 1 2 4

输出 #2

0

说明/提示

【样例 1 解释】

第一组可行的为 $i=1,j=4$，第二组可行的为 $i=2,j=4$ 。

【数据范围】

对于 $50 \%$ 的数据，有：$1 \le n \le 2 \times 10^3$ 。

对于所有测试数据，有：$1 \le n \le 2 \times 10^{5},1 \le P_i \le 10^9$ 。