因为贡献的方法是相加，一种想法就是拆开，对每一项单独贡献。
不难发现这题目中的贡献其实只涉及到两点之间。
即删除 \(x\) 时 \(y\) 也产生了贡献。
考虑这个贡献会在多少种排列中出现。
令 \(d = |x - y| + 1\)，即 \(x, y\) 中的点数。
能发现排列需要满足除 \(x\) 外的 \(d - 1\) 个点都必须出现在 \(x\) 之后，不然 \(x, y\) 就不连通了。
考虑用插板法的想法来计数。
即对于第 \(i + 1\) 次插入，此时有 \(i\) 个元素，\(i + 1\) 个空位可以插。
考虑先插入除 \(x\) 的 \(d - 1\) 个位置，方案数就为 \((d - 1)!\)。
接下来考虑插入 \(x\)，因为 \(x\) 必须在这些位置前面出现，所以对于 \(x\) 方案数就为 \(1\)。
对于之后的 \(n - d\) 个位置，也没有任何限制，方案数为 \(\frac{n!}{d!}\)。
于是方案数就为 \((d - 1)!\times \frac{n}{d!} = \frac{n!}{d}\)。
于是现在相当于就是对于每一个 \(y\) 求 \(\sum\limits_{x = 1}^n \frac{n!}{|x - y| + 1}\)。
考虑令 \(\operatorname{pre}_i = \sum\limits_{j = 1}^n \frac{n!}{d}\)。
对于这个绝对值，考虑拆成 \(x\le y\) 和 \(x\ge y\) 两部分，再减去 \(x = y\)。
于是可以化为 \(\operatorname{pre}_i + \operatorname{pre}_{n - i + 1} - \operatorname{pre}_1\)。
时间复杂度 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
ll inv[maxn], f[maxn], pre[maxn];
int main() {
int n; scanf("%d", &n);
ll fac = 1;
for (int i = 1; i <= n; i++)
(fac *= i) %= mod;
inv[0] = inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = inv[mod % i] * (mod - mod / i) % mod;
for (int i = 1; i <= n; i++)
f[i] = fac * inv[i] % mod;
for (int i = 1; i <= n; i++)
pre[i] = (pre[i - 1] + f[i]) % mod;
ll ans = 0;
for (int i = 1, x; i <= n; i++)
scanf("%d", &x), (ans += (pre[i] + pre[n - i + 1] - pre[1] + mod) * x) %= mod;
printf("%lld\n", ans);
return 0;
}