/***************************************************************************************************
 * author : Jie Chen (3rd Year CS)
 * school : Rochester Institute of Technology
 * created: 11.29.2024 20:33:38
****************************************************************************************************/
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;

#ifdef BROKEN_CODE
#include <bits/debug.h>
#else
#define dbg(...) 10082002
#define dbp(...) "Need Internship"
#endif

// Credit: Jiangly
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info range_query(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return range_query(2 * p, l, m, x, y) + range_query(2 * p + 1, m, r, x, y);
    }
    Info range_query(int l, int r) {
        return range_query(1, 0, n, l, r);
    }
    void range_apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        range_apply(2 * p, l, m, x, y, v);
        range_apply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void range_apply(int l, int r, const Tag &v) {
        return range_apply(1, 0, n, l, r, v);
    }
    template<class F>
    int find_first(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = find_first(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = find_first(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int find_first(int l, int r, F pred) {
        return find_first(1, 0, n, l, r, pred);
    }
    template<class F>
    int find_last(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = find_last(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = find_last(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int find_last(int l, int r, F pred) {
        return find_last(1, 0, n, l, r, pred);
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) {
        x += t.x;
    }
};
struct Info {
    int x = 0;
    int q = 0, p = -1;
    void apply(const Tag &t) {
        x += (p - q + 1) * t.x;
    }
};

int size(const Info& a) {
    return a.p - a.q + 1;
}
 
Info operator+(const Info &a, const Info &b) {
    Info c;
    // if (a.p == -1 && b.p == -1) {
    // } else if (a.p == -1) {
    //     c.q = b.q;
    //     c.p = b.p;
    // } else if (b.p == -1) {
    //     c.q = a.q;
    //     c.p = a.p;
    // } else {
    c.q = min(a.q, b.q);
    c.p = max(a.p, b.p);
    // }
    int Q = min(size(a), a.x);
    int P = min(size(b), b.x);
    c.x = Q + P;
    return c;
}

void work() {
    int n, k;
    cin >> n >> k;

    map<int, vector<int>> g;
    vector<int> a(n);
    vector<Info> init(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        init[i] = Info {0, i, i};
        g[a[i]].push_back(i);
    }

    map<int, int> pointer;
    i64 ans = 1LL * n * (n + 1) / 2;
    LazySegmentTree<Info, Tag> seg(init);
    for (int r = 0; r < n; r++) {
        int x = a[r];
        if (!pointer.contains(x)) {
            pointer[x] = -1;
        }
        int p = ++pointer[x];
        if (p >= k - 1) {
            if (p == k - 1) {
                seg.range_apply(0, g[x][0] + 1, {1});
            } else {
                seg.range_apply(g[x][p - k] + 1, g[x][p - k + 1] + 1, {1});
            }
        }
        if (p >= k) {
            if (p == k) {
                seg.range_apply(0, g[x][0] + 1, {-1});
            } else {
                seg.range_apply(g[x][p - k - 1] + 1, g[x][p - k] + 1, {-1});
            }
        }
        auto res = seg.range_query(0, r + 1);
        ans -= min(size(res), res.x);
        // dbg(res.q, res.p, res.x);
        // dbg(ans);
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    work();
}

// ~ Just Jie