Nocturne without a Moon
给定一个长度为 n 的排列 p1,p2,…,pn,其中每个从 1 到 n 的整数恰好出现一次。
求满足以下两个条件的下标四元组 (i,j,k,l) 的数量:
1≤i<j<k<l≤n,
pi⋅pk=pj⋅pl.
输入格式
第一行一个整数 n。
第二行 n 个整数 p1,p2,…,pn。
数据范围:
- 1≤n≤50000;
- 1≤pi≤n;
- 保证 p 是从 1 到 n 的排列。
输出格式
输出一行一个整数,表示满足条件的四元组数量。答案不取模。
样例输入 1
10
5 8 1 2 4 3 6 10 9 7
样例输出 1
4
样例说明
四个合法的下标四元组为:
- (1,3,4,8),因为 5⋅2=1⋅10;
- (1,4,5,8),因为 5⋅4=2⋅10;
- (1,6,7,8),因为 5⋅6=3⋅10;
- (2,5,6,7),因为 8⋅3=4⋅6。