#P18350. Nocturne without a Moon

Nocturne without a Moon

Nocturne without a Moon

给定一个长度为 nn 的排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,其中每个从 11 到 nn 的整数恰好出现一次。

求满足以下两个条件的下标四元组 (i,j,k,l)(i,j,k,l) 的数量:

1≤i<j<k<l≤n,1\le i<j<k<l\le n, pi⋅pk=pj⋅pl.p_i\cdot p_k=p_j\cdot p_l.

输入格式

第一行一个整数 nn。

第二行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n。

数据范围:

  • 1≤n≤50 0001\le n\le50\,000;
  • 1≤pi≤n1\le p_i\le n;
  • 保证 pp 是从 11 到 nn 的排列。

输出格式

输出一行一个整数,表示满足条件的四元组数量。答案不取模。

样例输入 1

10
5 8 1 2 4 3 6 10 9 7

样例输出 1

4

样例说明

四个合法的下标四元组为:

  • (1,3,4,8)(1,3,4,8),因为 5⋅2=1⋅105\cdot2=1\cdot10;
  • (1,4,5,8)(1,4,5,8),因为 5⋅4=2⋅105\cdot4=2\cdot10;
  • (1,6,7,8)(1,6,7,8),因为 5⋅6=3⋅105\cdot6=3\cdot10;
  • (2,5,6,7)(2,5,6,7),因为 8⋅3=4⋅68\cdot3=4\cdot6。