← 返回题目列表

Codeforces · 567/C

C. 几何级数

中文机器翻译题面 查看原题

Polycarp非常喜欢几何级数。由于他只有三岁,所以他只喜欢长度为三的进行。他还有一个最喜欢的整数 k 和一个由 n 个整数组成的序列 a。

他想知道从a中可以选出多少个长度为3的子序列,使它们形成公比为k的等比级数。

长度为 3 的子序列是三个索引 i1、i2、i3 的组合,即 1 ≤ i1 < i2 < i3 ≤ n。也就是说,长度为 3 的子序列是由三个元素组成的组,这些元素在序列中不一定是连续的,但它们的索引严格递增。

公比为 k 的等比级数是 b·k0、b·k1、...、b·kr - 1 形式的数字序列。

波利卡普只有三岁,所以他自己无法计算出这个数字。帮助他做到这一点。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 2·105),显示 Polycarp 的序列有多少个数字以及他最喜欢的数字。

第二行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — 序列的元素。

输出

输出一个数字 — 选择长度为 3 的子序列的方法数,使其形成具有公比 k 的等比级数。

示例

输入 #1

5 2
1 1 2 2 4

输出 #1

4

输入 #2

3 1
1 1 1

输出 #2

1

输入 #3

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

输出 #3

6

注意

在第一个样本测试中,答案是 4,因为可以选择两个 1 中的任意一个作为第一个元素,第二个元素可以是 2 中的任意一个,并且子序列的第三个元素必须等于 4。