分析

根据题意，我们可以得出是要求两两数字之间的差值的平方，由于数据很多，的暴力是肯定不行的。

那么我们只能写一个O(n)的算法，所以会想到求前缀和。

求解

这边由于都是差值，所以得进行一个转化，使得他成为前缀和的形式。

先排序，再两两做差即可。

int n;
scanf("%d",&n);
ll a[500010];
for (int i = 0;i < n;i ++) scanf("%lld",a + i); // 读入
sort(a,a + n); // 排序
n --; // 由于两两做差之后，数字个数就会减少1
for (int i = 0;i < n;i ++) {
    a[i] = a[i + 1] - a[i]; // 做差
}

接下来就可以进行找规律，从而写一个前缀和了。

找规律

假设有n = 5个数字，那么就有4个差，分别为：a,b,c,d。

那么两两做差就可以转化为连续和问题。

因此，题目所要求的过程即可转化为

因此，为了能够写出前缀和的形式，我们可以从左到右一个个数字来求和。

对于a，那么很简单只有；
对于b，那么则有
对于c，那么则有
对于d，那么则有

那么规律便来了，很容易发现：每一项都是上一个式子平方和中加上自己这一项。

我们可以对每一个式子展开：
对于a的式子，我们可以得到：
对于b的式子，我们可以得到：
对于c的式子，我们可以得到：
。。。

这样就不难得到一个递推关系。
设每一个差是，项所对应的平方和是，额外需要求和的（也就是上述式子中的）对应的是。
那么便可以写出:(i从1开始，)

最后答案就是对的求和了。

代码

实际写的时候大可不必分别开数组，可以直接用变量优化掉：

ll s = 0;
ll last = 0;
ll l = 0;
for (int i = 0;i < n;i ++) {
    l = l + i + 1 * a[i] * a[i] + 2 * a[i] * last;
    s = s + l;
    last = last + (i + 1) * a[i];
}

最后根据题目意思，加上mod即可，注意这边得开long long，不然容易溢出。

//
//  header_useful.h
//  c++_acm
//
//  Created by Jack on 2019/7/23.
//  Copyright © 2019 Jack. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it before "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return

/* header_useful_h */

int main()
{
    int n;
    scanf("%d",&n);
    ll a[500010];
    for (int i = 0;i < n;i ++) scanf("%lld",a + i);
    sort(a,a + n);
    n --;
    for (int i = 0;i < n;i ++) {
        a[i] = a[i + 1] - a[i];
    }
    ll s = 0;
    ll last = 0;
    ll l = 0;
    const int mod = 1000000007;
    for (int i = 0;i < n;i ++) {
        l = (l + ((i + 1) * ((a[i] * a[i]) % mod) % mod + (2 * a[i] * last) % mod) % mod) % mod;
        s = (s + l) % mod;
        last = (last + ((i + 1) * a[i]) % mod) % mod;
    }
    printf("%lld\n",s);
    return 0;
}