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


// sqrt-decomposition.

const ll B = 3000;



vector<ll> blk_adds;
vector<unordered_map<ll,ll>> blk_czs;
vector<ll> adds;

void add(ll l, ll r, ll x) {
    vector<bool> recalc(blk_adds.size());
    for(; l <= r; ) {
        if((l % B) == 0 && (l+B) <= r+1) {
            blk_adds[l/B] += x;
            l += B;
        } else {
            recalc[l/B] = true;
            adds[l] += x;
            l++;
        }
    }

    for(ll i = 0; i < recalc.size(); i++) {
        if(recalc[i]) {
            blk_czs[i] = {};
            for(ll j = i*B; j < min((ll)adds.size(), (i+1)*B); j++) {
                adds[j] += blk_adds[i];
                blk_czs[i][adds[j]]++;
            }
            blk_adds[i] = 0;
        }
    }
}

ll count_zero(ll l, ll r) {
    ll ans = 0;
    for(; l <= r; ) {
        if((l % B) == 0 && (l+B) <= r+1) {
           ans += blk_czs[l/B][-blk_adds[l/B]];
           l += B;
        } else {
            if(adds[l] + blk_adds[l/B] == 0) ans++;
            l++;
        }
    }
    return ans;
}


int main() {
    ll N, K; cin >> N >> K;

    unordered_map<ll,vector<ll>> indices;
    unordered_map<ll,ll> curs;

    vector<ll> A(N);
    for(ll i = 0; i < N; i++) {
        cin >> A[i];
        indices[A[i]].push_back(i);
    }


    blk_adds = vector<ll>(N/B + 1);
    blk_czs = vector<unordered_map<ll,ll>>(N/B + 1);
    for(auto& x: blk_czs) x[0] = B;
    adds = vector<ll>(N);

    for(auto& kv: indices) {
        kv.second.push_back(N);
        if(kv.second.size() > K) {
            add(kv.second[K-1], kv.second[K]-1,1);
        }
    }

    ll ans = 0;

    for(ll i = 0; i < N; i++) {
        ans += count_zero(i, N-1);

        auto& occs = indices[A[i]];
        if(occs.size() - curs[A[i]] > K) {
            add(occs[K-1 + curs[A[i]]], occs[K + curs[A[i]]], -1);
            curs[A[i]]++;
        }
        if(occs.size() - curs[A[i]] > K) {
            add(occs[K-1 + curs[A[i]]], occs[K + curs[A[i]]], 1);
        }
    }

    cout << ans << endl;




}