CBOJ Welcome Contest Problem 4 - Remainder Table

Points: 15 (partial)
Time limit: 1.5s
Memory limit: 128M

Author:
Problem type

We've all heard of the times table, but what about the remainder table?

Similar to the times table, the remainder table is a table used to define the modulo operator. The cell at $$(i, j)$$ will be equal to i % j.

Bob wants to test your knowledge on the remainder table! He has given you an array of $$N$$ positive integers $$A$$. Instead of i % j, he will ask you to get the value of A[i] % A[j], where $$(0 \le i, j \le N - 1)$$.

To make the checking process easier for Bob, he will simply ask you to output the sum of all $$N^2$$ cells. Can you do it fast enough?

Input Specification

The first line of the input will contain an integer $$N$$ $$(1 \le N \le 10^5)$$, indicating the length of the array $$A$$.

The next line of the input will contain $$N$$ integer ranging from $$1$$ to $$10^5$$ inclusive, denoting the values of the array $$A$$.

Output Specification

Output an integer, representing the sum of all $$N^2$$ cells in the remainder array.

$$1 \le N \le 1000$$

All the integers in the array will range from $$1$$ to $$10^3$$ inclusive.

$$1 \le N \le 10^5$$

All the integers in the array will range from $$1$$ to $$10^3$$ inclusive.

Sample Input

4
2 5 5 4

Sample Output

18

Sample Explanation

The table of remainder for $$[2, 5, 5, 4]$$ is as follows:

$$2$$$$5$$$$5$$$$4$$
$$2$$$$0$$$$1$$$$1$$$$0$$
$$5$$$$2$$$$0$$$$0$$$$4$$
$$5$$$$2$$$$0$$$$0$$$$4$$
$$4$$$$2$$$$1$$$$1$$$$0$$

The sum of $$1 + 1 + 2 + 4 + 2 + 4 + 2 + 1 + 1$$ is equal to $$18$$.