题面分析

这道题要求我们计算在给定的排列 p 中有多少个 (i, j) 对满足条件：

• $i < j$
• $p_i + p_j = i + j$

受到哈希3的启发，我们自然想到从左往右枚举每一个数$j$ , 维护一个前缀哈希表$H$，那么也就是在$i \in [1 , j - 1]$ 里寻找有多少个$i$ 满足:

本题为2024年9月1日字节跳动-秋招机考原题

字节跳动机考的介绍点击这里

题目内容

小红有一个长度为$n$的排列$p$，他想知道$p$中有多少个$i,j$对满足:$i< j$且$p_i+p_j=i+j$。

请你帮他算算吧。

输入描述

输入包含两行。

第一行一个正整数$n(1≤n≤200000)$，表示排列的长度。

第二行$n$个正整数$p_i(1≤p_i≤n)$，表示排列$p$。(保证输入是一个排列。)

输出描述

输出一行一个整数表示好对的个数。

样例1

输入

5
2 1 3 5 4

输出

4

说明

$p_1+p_2=2+1$，

$p_1+p_5=2+4$，

$p_2+p_4=1+5$，

$p_4+p_5=4+5$。

共这四对。