/***************************************************************************************************
 * 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

// constexpr int NAX = 1E5 + 10;
// struct Info {
//     int x = 0;
//     int tag = 0;
//     int a, b;
// } tr[4 * NAX];

// int n;

// void push(int p) {
//     if (tr[2 * p].a == tr[2 * p].b) {
//         tr[2 * p].x += tr[p].tag;
//     } else {
//         tr[2 * p].tag += tr[p].tag;
//     }
//     if (tr[2 * p + 1].a == tr[2 * p + 1].b) {
//         tr[2 * p + 1].x += tr[p].tag;
//     } else {
//         tr[2 * p + 1].tag += tr[p].tag;
//     }
//     tr[p].tag = 0;
// }

// int size(int p) {
//     return tr[p].b - tr[p].a + 1;
// }

// void pull(int p) {
//     int l = tr[2 * p].x + size(p) * tr[2 * p].tag;
//     int r = tr[2 * p + 1].x + size(p) * tr[2 * p + 1].tag;
//     if (tr[2 * p].a == tr[2 * p].b) {
//         l = min(l, 1);
//     }
//     if (tr[2 * p + 1].a == tr[2 * p + 1].b) {
//         r = min(r, 1);
//     }
//     tr[p].x = l + r;
// }

// void make_tree(int p, int l, int r) {
//     tr[p].a = l;
//     tr[p].b = r;
//     if (l == r) {
//         return;
//     }
//     int m = (l + r) / 2;
//     make_tree(2 * p, l, m);
//     make_tree(2 * p, m + 1, r);
// }

// void range_acc(int p, int l, int r, int x, int y, int v) {
//     if (l == x && r == y) {
//         if (l == r) {
//             tr[p].x += v;
//         } else {
//             tr[p].tag += v;
//         }
//         return;
//     }
//     push(p);
//     int m = (l + r) / 2;
//     if (y <= m) {
//         range_acc(2 * p, l, m, x, y, v);
//     } else if (x > m) {
//         range_acc(2 * p + 1, m + 1, r, x, y, v);
//     } else {
//         range_acc(2 * p, l, m, x, m, v);
//         range_acc(2 * p, m + 1, r, m + 1, y, v);
//     }
//     pull(p);
// }

// void range_acc(int l, int r, int v) {
//     dbp("ADDING");
//     dbg(l, r, v);
//     range_acc(1, 0, n - 1, l, r, v);
// }

// int range_query(int p, int l, int r, int x, int y) {
//     if (l == x && r == y) {
//         return tr[p].x + size(p) * tr[p].tag;
//     }
//     push(p);
//     int m = (l + r) / 2;
//     int ans = 0;
//     if (y <= m) {
//         ans += range_query(2 * p, l, m, x, y);
//     } else if (x > m) {
//         ans += range_query(2 * p + 1, m + 1, r, x, y);
//     } else {
//         ans += range_query(2 * p, l, m, x, m);
//         ans += range_query(2 * p, m + 1, r, m + 1, y);
//     }
//     pull(p);
//     return ans;
// }

// int range_query(int l, int r) {
//     return range_query(1, 0, n - 1, l, r);
// }

// 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 = 1E9;
    void apply(const Tag &t) {
        x += t.x;
    }
};

int size(const Info& a) {
    return a.p - a.q + 1;
}
 
Info operator+(const Info &a, const Info &b) {
    Info c;
    c.q = a.q;
    c.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, res = 0;
    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) {
            // dbp("INSIDE");
            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});
            }
        }
        ans -= seg.range_query(0, r + 1).x;
        // dbg(ans);
    }

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

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

// ~ Just Jie