给定一个长度为 $n$，值域为 $[1,k]$ 的序列 $a$，求出有多少个 $a$ 的子区间存在绝对众数。

$n,k \leq 5 \times 10^5$。

注意到绝对众数，每个区间只会存在一个绝对众数，那么不妨把每一个 存在绝对众数的 区间的贡献放在其绝对众数处计算！不妨钦定它为 $x$，那么现在就是要求出有多少个区间以 $x$ 为绝对众数，答案即是对所有 $x$ 求和。

现在对一个 $x$ 考虑：把 $a$ 中等于 $x$ 的数视为 $1$，否则视为 $-1$，记这个转化后的值为 $b_i$。则一个区间以 $x$ 为绝对众数当且仅当区间 $b$ 之和 $>0$。记 $s[l:r]$ 表示 $b_l+b_{l+1}+...+b_{r}$，即 $b$ 的区间和。

到这一步，其实对一个 $x$ 已经可以直接跑一遍逆序对求出答案了，时间复杂度 $O(kn\log n)$。根据 $\pm 1$ 序列逆序对做法可以做到 $O(Vn)$（维护移动过程 $a_i \to a_{i+1}$，计算移动后多出/减少的贡献，这个可以直接用桶 $O(1)$ 记录贡献）。

我们考察哪些位置可能被一个和 $>0$ 的区间 $[l,r]$ 覆盖，若 $b_i=1$，那么 $[i,i]$ 即为一种方案，否则若存在一个合法的 $[l,r]$ 满足 $i \in [l,r]$，则 $s[l:i],s[i:r]$ 中必有一个 $\geq 0$。综上，$i$ 能够被一个 $>0$ 的区间覆盖的必要条件是 $i$ 为端点的最大区间和 $\geq 0$。

考虑如何求出所有 $i$，以 $i$ 为右端点时为例，此时就是要求出所有前缀 $[1,i]$ 满足最大后缀 $\geq 0$。考虑从左到右扫一遍，维护当前的最大后缀 $mx$。每次在末尾加入 $b_i$ 等价于 $mx \to \mathrm{max}(mx+b_i,b_i)$，记 $cnt$ 表示序列中 $1$ 的个数，容易发现 $mx$ 的值最大达到 $cnt$，因此这种情况合法的总位置数是 $O(cnt)$ 的。同理，$i$ 为左端点时同样也只有 $O(cnt)$，因此直接暴力正反两遍扫描求得所有 $i$ 即可（连续的 -1 段可以直接暴力跳，根据前面对总位置数的分析这样是对的），使用归并排序求的最后的位置序列可以做到线性。

那么有可能成为一个 $>0$ 的区间端点的 $i$ 的个数也是 $O(cnt)$ 的。

直接把这些位置拿出来直接求逆序对就可以通过了，时间复杂度 $O(n\log n)$。

如何做到线性？注意到对于一个合法的连续段，其内的所有 $i$ 都会被拿出来，因此对于所有位置相邻的有效位置段，内部都可以用前面介绍的 $\pm 1$ 序列的线性做法求解，故而做到线性。

如果不写线性代码可以短很多，下面给出一份严格线性的实现：

const int N = 1.5e6 + 5;
int n, k, p[N], len, a[N], c[N];
vector<int> b1, b2, b;
vector<int> pos[N];
int t1[N], t2[N];

void solve() {
    cin >> n >> k;
    rep(i, 1, n) { int x; cin >> x; pos[x].pb(i); a[i] = x; }

    LL ans = 0;
    rep(v, 1, k) {
        if (!SZ(pos[v])) continue;
        
        len = SZ(pos[v]); p[len + 1] = n + 1;
        rep(i, 1, len) p[i] = pos[v][i - 1];

        b.clear(), b1.clear(), b2.clear();

        int now = 0;
        rep(i, 1, len) {
            int x = p[i] + 1;
            b1.pb(p[i]);
            now += 1;
            while (x < p[i + 1] && now >= 0)
                b1.pb(x), ++x, --now;
            tomax(now, 0);
        }
        now = 0;
        per(i, len, 1) {
            int x = p[i] - 1;
            b2.pb(p[i]);
            now += 1;
            while (x > p[i - 1] && now >= 0)
                b2.pb(x), --x, --now;
            tomax(now, 0);
        }

        reverse(all(b2));

        int i = 0, j = 0;
        while (i < SZ(b1) && j < SZ(b2)) {
            if (b1[i] < b2[j]) {
                if (b.empty() || b1[i] != b[SZ(b) - 1])
                    b.pb(b1[i]);
                ++i;
            }
            else {
                if (b.empty() || b2[j] != b[SZ(b) - 1])
                    b.pb(b2[j]);
                ++j;
            }
        }
        while (i < SZ(b1)) {
            if (b.empty() || b1[i] != b[SZ(b) - 1])
                 b.pb(b1[i]);
            ++i;
        }
        while (j < SZ(b2)) {
            if (b.empty() || b2[j] != b[SZ(b) - 1])
                b.pb(b2[j]);
            ++j;
        }

        j = 0;
        for (auto x: b) {
            while (j < len && p[j + 1] <= x) ++j;
            t1[x] = j - (x - j) + n;
            t2[x] = t1[x] - (a[x] == v? 1: -1);
        }

        int lst = 0, nowv = 1, w = 0;
        for (auto x: b) {
            if (x ^ (lst + 1))
                nowv = t1[x], w = 0;
            lst = x;
            ++c[t2[x]], w += (t2[x] < nowv);
            while (nowv < t1[x]) w += c[nowv++];
            while (nowv > t1[x]) w -= c[--nowv];
            ans += w;
        }

        for (auto x: b)
            c[t2[x]] = 0;
    }
    cout << ans << '\n';
}