#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
const int sz = 1e6 + 6, mod = 1e9 + 7;
int arr[sz], cur_ct[sz];
std::vector<int> id[sz];
struct bol {
    int mx, lz, cnt;
    bol() {
        mx = lz = cnt = 0;
    }
};
struct segment_tree{
    std::vector<bol> t;
    int n;
    segment_tree(int _n) {
        t.resize(4 * _n + 1);
        n = _n;
        build(1, 1, n);
    }
    void build(int node, int l, int r) {
        if(l == r) {
            t[node].cnt = 1;
            return; 
        }
        int mi = (l + r) / 2;
        build(2 * node, l, mi);
        build(2 * node + 1, mi + 1, r);
        t[node] = merge(t[2 * node], t[2 * node + 1]);
        return;
    }
    bol merge(bol a,bol b) {
        bol c;
        c.mx = max(a.mx, b.mx);
        c.cnt = (a.mx == c.mx) * a.cnt + (b.mx == c.mx) * b.cnt;
        return c;
    }
    int chk(int a,int b,int c,int d) {
        if(a > b || a > d || c > d || c > b)
            return 1;
        return 0;
    }
    void lzy_down(int node) {
        if(t[node].lz) {
            t[2 * node].lz += t[node].lz;
            t[2 * node].mx += t[node].lz;

            t[2 * node + 1].lz += t[node].lz;
            t[2 * node + 1].mx += t[node].lz;
        }
        t[node].lz = 0;
    }
    void update(int node, int l, int r, int le, int ri, int vala) {
        if(chk(l, r, le, ri))
            return;
        if(l >= le && r <= ri) {
            t[node].lz += vala;
            t[node].mx += vala;
            return;
        }
        lzy_down(node);
        int mi = (l + r) / 2;
        update(2 * node, l, mi, le, ri, vala);
        update(2 * node + 1, mi + 1, r, le, ri, vala);
        t[node] = merge(t[2 * node], t[2 * node + 1]);
        return;
    }
    void update(int le, int ri, int vala) {
        update(1, 1, n, le, ri, vala);
    }
};
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k; cin >> n >> k;
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        id[arr[i]].push_back(i);
    }
    segment_tree seg(n);
    for(int i = 1; i <= n; i++) {
        int a = arr[i];
        int ind = cur_ct[a];
        ind++;
        if(ind >= k) {
            int l = 1, r = id[a][ind - k];
            if(ind > k) {
                l = id[a][ind - k - 1] + 1;
                int l1 = 1;
                if(ind > k + 1) l1 = id[a][ind - k - 2] + 1;
                seg.update(l1, l - 1, 1);
            } 
            seg.update(l, r, -1);
        }
        if(seg.t[1].mx >= 0) ans += seg.t[1].cnt - n + i;
    }
    cout << ans << "\n"; 
    return 0; 
}