CF567C Geometric Progression

Polycarp 只有三岁，他只喜欢长度为 $3$ 的序列。他还有一个最喜欢的整数 $k$ 和一个序列 $a$，$a$ 是由 $n$ 个整数组成的。 他想知道从 $a$ 中可以选择多少个长度为 $3$ 的子序列，使得这个子序列形成一个公比 $k$ 的几何级数。 长度为 $3$ 的子序列是指在序列中找到 $3$ 个元素。如果这 $3$ 个元素的下标依次为 $i_1,i_2,i_3$，那么需要满足 $1 \le i_1 < i_2 < i_3 \le n $。也就是说，这些元素在序列中不一定连续，但它们的下标应当是递增的。 公比 $k$ 的几何级数形式为 $b \times k^0,b \times k^1,\cdots,b \times k^{r-1}$。

输入的第一行包含两个整数，$n$ 和 $k$。保证 $1 \le n,k \le 2 \times 10^5$。$n$ 表示 Polycarp 的序列数字总个数，$k$ 表示他最喜欢的数字个数。 第二行包含 $n$ 个整数，$a_1,a_2, \cdots ,a_n$，保证 $-10^9 \le a _ i \le 10^9$。

输出一个数字，表示可以构成公比为 $k$ 的几何级数的长度为 $3$ 的子序列的数目。

In the first sample test the answer is four, as any of the two 1s can be chosen as the first element, the second element can be any of the 2s, and the third element of the subsequence must be equal to 4.