//题目回忆:给定一个序列，求两两和除以1e8的余数
//错误思路，每个数都要累加n-1次，累加直接mod 1e8
//显然是错误的，因为有的值不满1e8，不需要取模
//正确做法：当不好统计时，可以考虑总数-对立面，我们观察到数据范围，每个数恰巧小于1e8，因此两个数的和不可能超过2e8，因此当两个数和超过1e8时，取模相当于-1e8，和小于1e8则直接相加，我们仅需统计需要减去多少1e8即可
//统计区间，且数字顺序对答案无影响，可以考虑sort+二分，统计答案即可
#include <iostream>

using namespace std;

const int N = 3e5+10,MOD = 1e8;

typedef long long LL;

LL s[N];
LL a[N];

int main()
{
    LL n;
    cin>>n;
    LL sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];a#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e5+10,MOD = 1e8;

typedef long long LL;

LL n;
int a[N];

int main()
{
    LL sum=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=(n-1)*a[i];
    }
    sort(a,a+n);
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        int l=i+1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a[i]+a[mid]>=1e8) r=mid;
            else l=mid+1;
        }
        cnt+=(n-l);
    }
    cout<<sum-cnt*100000000;
}
    }
    for(int i=1;i<=n-1;i++)
        sum=(sum+s[n]-s[i]+(n-i)*a[i])%MOD;
    cout<<sum+100000000;
}