На отборочном туре олимпиады вы решали задачу «Хорошие пары». Напомним, что неупорядоченная пара натуральных чисел называется хорошей, если одно из них делится на другое.
При подготовке задачи с отборочного тура жюри столкнулось со следующей проблемой. Чтобы проверить правильность решения, необходимо уметь быстро находить количество хороших пар, которые можно составить из чисел, выведенных программой участника. Жюри смогло справиться с данной проблемой, а сможете ли вы?
Более формально: вам даются $$$n$$$ натуральных чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. Найдите количество таких пар индексов $$$i$$$, $$$j$$$, где $$$i \lt j$$$, что $$$a_i$$$ делится на $$$a_j$$$ или $$$a_j$$$ делится на $$$a_i$$$.
В первой строке входных данных вводится натуральное число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество чисел.
В следующих $$$n$$$ строках вводятся целые числа $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, где $$$1 \le a_i \le 10^6$$$.
Выведите одно целое число — количество хороших пар, которые можно составить из входных чисел.
Подзадача 1 (до 20 баллов): $$$n \le 1000$$$.
Подзадача 2 (до 40 баллов): все $$$a_i$$$ не превышают 1000.
Подзадача 3 (до 40 баллов): нет дополнительных ограничений.
32510
2
211
1
Обратите внимание, что ответ может превышать возможное значение 32-битной целочисленной переменной. Поэтому необходимо использовать 64-битный целочисленный тип данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). В языке Python ничего дополнительно делать не требуется.
