C0779 符文的共鸣
符文的共鸣
题目描述
在魔法世界中，有 n 个符文，每个符文有一个能量值 ai 。当两个符文共鸣时，会产生能量，但能量过高时会溢出，只保留剩余部分。
具体来说，符文 i 和符文 j 共鸣产生的能量为 (ai + aj ) mod 100000000。
请计算所有不同的符文对（即所有 i < j 的配对）共鸣能量的总和。
输入
第一行输入一个整数 n。
第二行输入 n 个整数 a1 , a2 , ……, an 。
输出
输出一个整数，表示所有符文对共鸣能量的总和。
数据范围
2≤N≤100000，1≤a ≤10^8
输入样例1
2
1 1
输出样例1
2
输入样例2
2
99999999 99999999
输出样例2
99999998