思路

用 $c_x$ 表示数值 $x$ 在序列中的出现次数。先按公比是否为 $1$ 分类，避免把不同下标与不同数值混淆。

公比为 $1$ 时，三个数值相同。选取三个互不相同的下标并按顺序放入三元组，有 $c_x(c_x-1)(c_x-2)$ 种方法。

公比 $b\ge2$ 时，三个数值严格递增，依次为 $x,xb,xb^2$。它们的下标天然不同，因此贡献为 $c_xc_{xb}c_{xb^2}$。数值的递增顺序已经固定三元组的位置，不应再乘以 $6$，也不应要求下标递增。

做法

先统计每种数值的频率，并记录实际出现过的数值以及最大值 $M$。

对每个出现过的 $x$，加入公比为 $1$ 的贡献，再枚举整数 $b\ge2$，直到 $xb^2>M$。若三个数值均出现，就加入它们频率的乘积。

使用固定值域的频率数组。每组结束后只清空本组出现过的位置，避免每组都重新初始化整个值域。所有计数与乘法均使用 64 位整数。

正确性证明

任意魔法三元组有唯一的公比 $b=a_j/a_i$。当 $b=1$ 时，三个数值相同，按顺序选择不同下标的方案数正是下降阶乘 $c_x(c_x-1)(c_x-2)$。

当 $b\ge2$ 时，三个数值严格递增，必然唯一表示为 $x,xb,xb^2$，且最大值不超过 $M$，所以该组 $(x,b)$ 一定被枚举。反过来，任意被枚举的 $(x,b)$ 中，从三种数值各选一个下标就得到合法三元组，共有三者频率乘积种方法。

这两类互不相交，每个三元组都被唯一计数，因此算法正确。

部分分做法

子任务 1 枚举三个下标，直接检查下标互异与两次整数倍关系，复杂度为 $O(n^3)$。

子任务 2 枚举前两个下标。若 $a_j$ 能被 $a_i$ 整除，就唯一确定公比及第三个数值，用频率数组直接得到第三个下标的选择数。当公比为 $1$ 时，要扣除已用的两个下标，复杂度降为 $O(n^2)$。

子任务 3 先处理公比为 $1$ 的情况，再枚举两种不同数值 $x<y$。若 $y$ 能被 $x$ 整除，第三个数值为 $y^2/x$，贡献为三种数值的频率乘积。在小值域内，不同数值数量很少，可用 $O(U^2)$ 的数值对枚举处理很长的序列。

一般情形利用 $xb^2\le M$ 的限制直接枚举公比，进一步消除对所有第二个数值的枚举。

复杂度

设 $U$ 为当前测试中不同数值的数量。排序不是必需的，频率统计及清理需要 $O(n+U)$ 时间。

枚举公比的次数为 $\sum_{x:c_x>0} O(\sqrt{M/x})$。将出现过的值从小到大排列，第 $i$ 个值至少为 $i$，故该和为 $O(\sqrt{MU})$。每组时间复杂度为 $O(n+\sqrt{MU})$，固定频率数组和输入序列占用 $O(10^6+n)$ 空间。多测时对各组的实际工作量求和，频率数组只初始化一次。

答案不超过全部有序不同下标三元组的数量 $n(n-1)(n-2)$，在 $n=200000$ 时为 $7999880000400000$，使用有符号 64 位整数足够。