该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于正整数 $x,y$，我们定义 $f(x,y)$ 为「$(x+y)$ 除以 $10^8$ 的余数」。

给定长度为 $N$ 的正整数序列 $A=(A_1,\ldots,A_N)$，请计算以下表达式的值：

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)$

输入

第一行包含一个整数 $N$ ($2 \leq N \leq 3 \times 10^5$)，表示序列的长度。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$ ($1 \leq A_i < 10^8$)，表示序列 $A$。

输出

输出一个整数，表示所求表达式的值。

样例

3
3 50000001 50000002

100000012

5
1 3 99999999 99999994 1000000

303999988

说明

样例 1 解释

• $f(A_1,A_2)=50000004$
• $f(A_1,A_3)=50000005$
• $f(A_2,A_3)=3$

所以答案是 $f(A_1,A_2)+f(A_1,A_3)+f(A_2,A_3) = 100000012$

请注意，我们不是求总和除以 $10^8$ 的余数。