Это сложная версия задачи. Единственное отличие в том, что в этой версии \(a_i \le 10^9\).
Для данной последовательности целых чисел \(a\) длины \(n\), тройка \((i, j, k)\) называется магической, если
- \(1 \le i, j, k \le n\).
- \(i\), \(j\), \(k\) — попарно различны.
- существует некоторое целое положительное число \(b\), такое что \(a_i \cdot b = a_j\), а \(a_j \cdot b = a_k\).
Коля получил в подарок последовательность целых чисел \(a\), и теперь хочет посчитать количество магических троек для нее. Помогите ему в этом!
Обратите внимание, что нет ограничений на порядок чисел \(i\), \(j\) и \(k\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество магических троек для последовательности \(a\).
Примечание
В первом примере существует \(6\) магических троек для последовательности \(a\) — \((2, 3, 5)\), \((2, 5, 3)\), \((3, 2, 5)\), \((3, 5, 2)\), \((5, 2, 3)\), \((5, 3, 2)\).
Во втором примере существует единственная магическая тройка для последовательности \(a\) — \((2, 1, 3)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
|
6
1
3
0
9
16
45
|