[R77F]巡检 - 代码源竞赛平台

时空限制

1S/512M

题目描述

一条展廊中从左到右摆放着 $n$ 件展品，位置依次编号为 $1,2,\ldots,n$。位置 $i$ 上展品的编号为 $p_i$，所有展品的编号恰好是 $1,2,\ldots,n$，每个编号出现一次。

巡检员准备选择一段连续的位置 $[l,r]$。设这一段中编号最小的展品位于位置 $u$，编号最大的展品位于位置 $v$。如果这两件展品的位置关于所选区间的中心对称，也就是

$$u+v=l+r,$$

那么这段区间就符合巡检要求。这里的 $u,v$ 均为展品在整条展廊中的位置编号。

请计算符合巡检要求的非空区间数量。长度为 $1$ 的区间也参与统计，此时 $u=v=l=r$。

格式

输入格式

第一行包含一个正整数 $n$，为展品的数量。

第二行包含 $n$ 个正整数 $p_1,p_2,\ldots,p_n$，其中 $p_i$ 为位置 $i$ 上展品的编号。

输出格式

输出一个正整数，表示符合巡检要求的非空区间数量。

样例

样例输入 #1

3
1 2 3

样例输出 #1

6

样例解释 #1

全部六个非空区间都符合要求。

样例输入 #2

3
2 1 3

样例输出 #2

5

样例解释 #2

只有区间 $[1,3]$ 不符合要求。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$10$	$9$	无
$2$	$25$	$3000$
$3$	$20$	$2 \times 10^5$	A
$4$	$45$		无

特殊性质 A：存在一个整数 $k$，满足 $0\le k<n$，将排列 $p$ 的前 $k$ 个数按原顺序移到末尾后，得到的排列为 $1,2,\ldots,n$ 或 $n,n-1,\ldots,1$。

对于 $100\%$ 的数据，满足 $1\le n\le 2 \times 10^5$，且 $p$ 是 $1,2,\ldots,n$ 的排列。