#P18770. Know Your Powers

Know Your Powers

Know Your Powers

对于非负整数 kk 和正整数 nn,记 σk(n)\sigma_k(n) 为 nn 的所有正约数的 kk 次方之和:

σk(n)=∑d∣ndk.\sigma_k(n)=\sum_{d\mid n}d^k.

给定 nn 个整数 a1,…,ana_1,\ldots,a_n,求

∑1≤i<j≤nσ1(ai+aj).\sum_{1\le i<j\le n}\sigma_1(a_i+a_j).

输入格式

第一行一个整数 nn(2≤n≤40002\le n\le4000)。

第二行 nn 个正整数 a1,…,ana_1,\ldots,a_n(1≤ai≤1091\le a_i\le10^9),以空格分隔。

输出格式

输出一个整数,表示所求的和。不对任何数取模。

样例

输入:

5
1 2 3 4 5

输出:

91