CF190D

// Problem: D. Non-Secret Cypher
// Contest: Codeforces - Codeforces Round 120 (Div. 2)
// URL: https://codeforces.com/problemset/problem/190/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifdef __DEBUG__
#include "dbg.h"
#else
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main0(int argc, char **argv)
{
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (auto &x : a)
        cin >> x;
    ll ans = 0;
    map<int, int> cnt;
    int last_hit = -1;
    bool satisfy = false;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && !satisfy) {
            cnt[a[j]]++;
            if (cnt[a[j]] >= k)
                satisfy = true, last_hit = a[j];
            ++j;
        }
        dbg(i, j, last_hit, n - j + 1);
        ans += (last_hit == -1 ? 0 : n - j + 1);
        if (a[i] == last_hit)
            satisfy = false, last_hit = -1;
        cnt[a[i]]--;
    }
    cout << ans << endl;
    return 0;
};

int main(int argc, char **argv)
{
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (auto &x : a)
        cin >> x;
    map<int, int> cnt;
    ll ans = 0;
    int left = 0;
    for (auto x : a) {
        cnt[x]++;
        while (cnt[x] >= k) {
            cnt[a[left]]--;
            ++left;
        }
        ans += left;
    }
    cout << ans << endl;
    return 0;
};