Editorial for Consecutive Neighbours

Approach

Let $I_i$ be the indicator that values $i$ and $i + 1$ occupy adjacent positions in the permutation. The total score is

$X = \sum_{i=1}^{n-1} w_i I_i$.

By linearity,

$E[X] = \sum_{i=1}^{n-1} w_i \Pr(I_i = 1)$.

To compute the probability, glue $i$ and $i + 1$ into a single block. The block may be ordered in $2$ ways, and the remaining $n - 1$ objects (the block plus $n - 2$ other values) may be permuted freely, so

$\Pr(I_i = 1) = \frac{2 \cdot (n - 1)!}{n!} = \frac{2}{n}$.

A common mistake is to answer $2/(n - 1)$: after placing $i$, two of the remaining $n - 1$ slots look adjacent, but that count is wrong at the two endpoints of the array, where $i$ has only one neighbour slot. Averaging over the position of $i$ recovers $2/n$.

Therefore

$E[X] = \frac{2}{n} \sum_{i=1}^{n-1} w_i$.

The indicators are dependent (overlapping pairs cannot all be adjacent at once in general), but linearity still applies. The implementation is $O(n)$.

Solution (C++)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

long long modpow(long long a, long long e) {
    long long r = 1;
    a %= MOD;
    while (e) {
        if (e & 1) {
            r = r * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << "\n";
        return 0;
    }
    long long sum = 0;
    for (int i = 0; i < n - 1; i++) {
        long long w;
        cin >> w;
        sum += w;
        if (sum >= MOD) {
            sum %= MOD;
        }
    }
    sum %= MOD;
    cout << 2 * sum % MOD * modpow(n, MOD - 2) % MOD << "\n";
}