【正经题解】262144 Revisit

维护两个数组 $pre$ 和 $nex$ ，表示每个位置向左和向右最近的相同数字的位置。
对于每个数字，记录它在原数组中的位置。
初始化当前的最小最终数字之和 $cur$ 为总长度 $n$ 乘以 $n$ $+$ $1$ 除以 $2$ ，即所有数字之和。
遍历每个数字，合并相邻两个数字，并更新 $cur$ 。如果合并后的子段大小大于 $1$ ，记录该位置。
重复上述过程，直到所有的子段大小都为 $1$ 。
输出最终的最小最终数字之和。

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

#define fi first
#define se second

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long LL;

const int N = 3e5 + 5, M = 1e6 + 35;

int n, a[N], pre[N], nex[N];
LL cur;
vi p[M];
list<pi> seg[N];

LL sum(int l, int r) {
    return 1LL * (l + r) * (r - l + 1) / 2;
}

LL calc(list<pi> L) {
    LL ret = 0;
    for (auto it = L.begin(); it != L.end(); it++) {
        auto [x, y] = *it;
        if (next(it) == L.end()) {
            ret += sum(1, y - x);
            break;
        } else {
            int nx = next(it)->fi;
            ret += 1LL * (nx - x) * y - sum(x, nx - 1);
        }
    }
    return ret;
}

void upd(list<pi> &L) {
    if (L.size() <= 1)
        return;
    cur += calc(L);
    int mx = -1;
    list<pi> nL;
    auto it = L.begin();
    for (auto [x, y] : L) {
        while (next(it) != L.end() && next(it)->fi <= y)
            it++;
        if (it->se > mx) {
            nL.push_back({x, mx = it->se});
        }
    }
    swap(L, nL);
    cur -= calc(L);
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]].push_back(i);
    }

    cur = 1LL * n * (n + 1) / 2;

    for (int i = 1; i <= n; i++)
        pre[i] = nex[i] = i;

    LL ans = 0;
    vi q;

    for (int v = 1; cur > 0; v++) {
        ans += cur;
        vi nq;

        // 遍历上一轮得到的所有起始位置
        for (auto l : q) {
            upd(seg[l]);
            if (seg[l].size() > 1)
                nq.push_back(l);
        }

        // 遍历当前数值的位置
        for (auto i : p[v]) {
            int l = pre[i], r = nex[i + 1];
            bool add = seg[l].size() <= 1;
            nex[l] = r, pre[r] = l;
            seg[l].push_back({i, i + 1});
            cur--;
            seg[l].splice(seg[l].end(), seg[i + 1]);
            add &= seg[l].size() > 1;
            if (add)
                nq.push_back(l);
        }

        swap(q, nq);
    }

    cout << ans << "\n";

    return 0;
}