Với một tập ~S~ chứa tất cả các kết quả của từng đoạn ~[L, R]~ thỏa ~1 \le L \le R \le n~, Với từng ~x \in S~, và ~p(x)~ là xác xuất của kết quả ~x~. Ta có công thức ~EV~ như sau:

Ta có:

Với ~\Omega~ là không gian mẫu và ~\Omega = n^2~ (mọi cặp ~L, R~ có thể), và ~C(x)~ là số lượng cặp ~L, R~ sẽ cho ra kết quả là ~x~.

Lúc này ta có:

Việc tính ~C(x)~ cho từng ~x~ là khá khó. Vì thế với từng giá trị khác nhau có trong ~a_1, a_2, \cdots, a_{n - 1}, a_n~, ta định nghĩa ~f(x) = \text{số lượng đoạn [L, R] chứa 'x'}~

Đặt ~T = \{ a_1, a_2, \cdots, a_{n - 1}, a_n \}~, là tập hợp các phần khác nhau của dãy ~a~

Ta có:

Việc tính ~f(y)~ thì dễ hơn, ta có thể tính phần bù của số lượng những đoạn không chứa ~x~, ta có ~pos = \{0, pos_1, pos_2, \cdots, pos_k, n + 1 \}~ là tập gồm ~k + 2~ phần tử (với ~k~ là số lần ~x~ xuất hiện) chứa các vị trí của xuất hiện của ~x~ theo thứ tự tăng dần chỉ số, và có ~pos_0 = 0~ và ~pos_{k + 1} = n + 1~, khi đó ta có thể tính:

Vậy ta có:

Chứng minh ~(1)~:

Giả sử một cặp ~L_0, R_0~ cố định cho ra kết quả là ~x~, có nghĩa là trong tổng mà ta đang tính, cặp ~L_0, R_0~ sẽ được tính ~x~ lần.

Cùng cặp ~L_0, R_0~ đó, có nghĩa ta có ~x~ giá trị ~a_i~ khác nhau trong đoạn ~[L_0, R_0]~

Với từng ~a_i~ trong đoạn ~[L_0, R_0]~, trong từng ~f(a_i)~ mà ta tính, chắc chắn đã tính ~[L_0, R_0]~ đúng một lần. Vì vậy với ~x~ giá trị ~a_i~ khác nhau trong ~[L_0, R_0]~ và sau ~x~ lần tính ~f(a_i)~ thì ~[L_0, R_0]~ cũng sẽ được tính đủ ~x~ lần.

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;

#define int int64_t

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int n, last[MAXN];

int multiply_modulo(int a, int b) {
    if (b == 0) return 0;
    int t = multiply_modulo(a, b / 2) % MOD;
    if (b & 1) return ((t + t) % MOD + a % MOD) % MOD;
    else return (t + t) % MOD;
}

int power_modulo(int a, int b) {
    if (b == 0) return 1;
    int half = power_modulo(a, b / 2) % MOD;
    half = multiply_modulo(half, half);
    if (b & 1) return multiply_modulo(half, a);
    else return half;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    int cnt = 0, sum = 0;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        sum += cnt + i - last[x];
        cnt += i - last[x];
        last[x] = i;
    }

    int res = (sum * 2 - n) % MOD * power_modulo(n * n, MOD - 2) % MOD; 
    cout << res;
}