题目描述

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$ 的子序列的数目。

5 2
1 1 2 2 4

4

3 1
1 1 1

1

10 3
1 2 6 2 3 6 9 18 3 9

6