Задача D. Кратные тройки

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  
Максимальный балл:20  

Условие

Дана последовательность различных целых чисел A1, A2, …, AN. Требуется подсчитать количество таких троек (Ai, Aj, Ak), что i ≠ j, i ≠ k, j < k и Ai нацело делится как на Aj, так и на Ak. Например, в последовательности 1 3 2 4 6 таких троек четыре: 6 3 2, 6 1 3, 6 1 2, 4 1 2.

Рекомендуется рассмотреть частичные решения для следующих случаев

Формат входного файла

Входной файл содержит число N, за которым следуют N чисел A1 A2… AN.

Формат выходного файла

Выходной файл должен соджержать единственное число — количество троек.

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
0
2
4 2 4 8 16
4

0.034s 0.006s 15