include <bits></bits>

using namespace std;

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

int N, K;
cin >> N >> K;
vector<long long> a(N);
for(int i = 0; i < N; i++) cin >> a[i];

unordered_map<long long, vector<int>> pos;
pos.reserve(N * 2);

for(int i = 0; i < N; i++)
    pos[a[i]].push_back(i + 1);

long long ans = 0;

for(auto &p : pos){
    auto &v = p.second;
    int t = v.size();
    if(t < K) continue;

    for(int i = 0; i + K - 1 < t; i++){
        for(int j = i + K - 1; j < t; j++){
            int c = j - i + 1;
            int maxLen = 2 * c - 1;

            int Lmin = v[j] - maxLen + 1;
            int Lmax = v[i];

            int Rmin = v[j];
            int Rmax = v[i] + maxLen - 1;

            Lmin = max(Lmin, 1);
            Lmax = min(Lmax, v[i]);

            Rmin = max(Rmin, v[j]);
            Rmax = min(Rmax, N);

            if(Lmin > Lmax || Rmin > Rmax) continue;

            long long total = 1LL * (Lmax - Lmin + 1) * (Rmax - Rmin + 1);
            ans += total;
        }
    }
}

cout << ans;

}

Cho mảng gồm 𝑁 N số nguyên dương 𝐴 1 , 𝐴 2 , … , 𝐴 𝑁 A 1 ​

,A 2 ​

,…,A N ​

và một số nguyên 𝐾 K.

Một đoạn con liên tiếp [ 𝐿 , 𝑅 ] [L,R] được gọi là K-dominant nếu tồn tại một giá trị 𝑋 X sao cho:

số lần xuất hiện của 𝑋 X trong đoạn lớn hơn tổng số lần xuất hiện của tất cả các giá trị khác trong đoạn (tức là 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) > ( 𝑅 − 𝐿 + 1 ) − 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) freq(X)>(R−L+1)−freq(X))

và đồng thời 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) ≥ 𝐾 freq(X)≥K.

Hãy đếm số lượng đoạn con K-dominant.

Ràng buộc:

1 ≤ 𝑁 ≤ 2 × 10 5 1≤N≤2×10 5

1 ≤ 𝐴 𝑖 ≤ 10 9 1≤A i ​

≤10 9

1 ≤ 𝐾 ≤ 𝑁 1≤K≤N

Input:

N K A1 A2 ... AN

Output: In ra một số nguyên là số đoạn con K-dominant.

Ví dụ:

Input 6 2 1 2 2 2 3 2

Output 7