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