#include "bits/stdc++.h"

using namespace std;

#ifndef ONLINE_JUDGE
#include "test.h"
#else
#define debug(...) 42
#define debug_assert(...) 42
#endif
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using ll = long long;
using ull = unsigned long long;
#define irep(i, l, r) for(int i = l; i <= r; ++ i)
#define endl '\n'
#define int ll

using VI = vector<int>;
using VII = vector<VI>;
using PII = pair<int, int>;
const int inf = 1e18;
const int mod = 1e9 + 7;

struct nodes {
    int len, val, sum;

    nodes() {
        len = 0;
        val = 0;
        sum = 0;
    }
};

vector<int> node[1000000 + 7];

void init() {
    int n, k;
    cin >> n >> k;
    VI arr(n + 1);
    // map<int, vector<int>> node;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        node[arr[i]].emplace_back(i);
    }
    // 前两个存储删除空间，后两个存储添加的空间
    // vector<array<int, 4>> e(n + 1);
    // irep(i, 1, n){
    //
    // }
    // for (const auto&[_, v]: node) {
    //     for (int i = 0; i < v.size(); i++) {
    //         int len = v[i];
    //         if (i == 0) {
    //             e[len][0] = e[len][1] = 0;
    //         }
    //         else {
    //             int before = v[i - 1];
    //             e[len][0] = e[before][2];
    //             e[len][1] = e[before][3];
    //         }
    //         if (i + k - 1 > v.size() - 1) {
    //             e[len][2] = n + 1;
    //         }
    //         else {
    //             e[len][2] = v[i + k - 1];
    //             if (i + k > v.size() - 1) {
    //                 e[len][3] = n + 1;
    //             }
    //             else {
    //                 e[len][3] = v[i + k];
    //             }
    //         }
    //     }
    // }

    vector<nodes> _sg(4000000);

    auto pushup = [&](int q) {
        if (_sg[q].val) _sg[q].sum = _sg[q].len;
        else _sg[q].sum = _sg[q << 1].sum + _sg[q << 1 | 1].sum;
    };
    function<void(int,int)> addval = [&](int q,int v) {
        _sg[q].val += v;
        if (_sg[q].val < 0) {
            // addval(q << 1, _sg[q].val);
            // addval(q << 1 | 1, _sg[q].val);
            _sg[q].val = 0;
        }
        pushup(q);
    };

    auto pushdown = [&](int q) {
        addval(q << 1, _sg[q].val);
        addval(q << 1 | 1, _sg[q].val);
        _sg[q].val = 0;
    };

    function<void(int,int,int)> build = [&](int q,int l,int r) {
        if (l == r) {
            _sg[q].len = 1;
            return;
        }
        int mid = (l + r) / 2;
        build(q << 1, l, mid);
        build(q << 1 | 1, mid + 1, r);
        _sg[q].len = _sg[q << 1].len + _sg[q << 1 | 1].len;
    };

    function<void(int,int,int,int,int,int)> add = [&](int q,int v,int l,int r,int L,int R) {
        if (L <= l && r <= R) {
            addval(q, v);
            return;
        }
        if (r < L || l > R)return;
        // pushdown(q);
        int mid = (l + r) / 2;
        if (mid >= L) {
            add(q << 1, v, l, mid, L, R);
        }
        if (mid < R) {
            add(q << 1 | 1, v, mid + 1, r, L, R);
        }
        pushup(q);
    };

    // debug(e);
    int ans = 0;
    build(1, 1, n);

    // for (int i = 1; i <= n; i++) {
    //     auto [f1,t1,f2,t2] = e[i];
    //     if (f1 != 0 && f1 != n + 1) {
    //         debug("add", -1, f1, min(t1, n));
    //         add(1, -1, 1, n, f1, min(t1, n));
    //     }
    //     if (f2 != 0 && f2 != n + 1) {
    //         debug("add", 1, f2, min(t2, n));
    //         add(1, 1, 1, n, f2, min(t2, n));
    //     }
    //     ans += _sg[1].sum;
    //     debug(_sg[1].sum);
    // }
    // cout << ans << endl;
    vector<array<int, 4>> opt; // time = 0, add (3) from (1) to (2)
    irep(i, 1, 1e6) {
        node[i].emplace_back(n + 1);
        int sz = node[i].size();
        // cerr << sz << endl;
        int lst = 0;
        for (int p = 0, q = p + k - 1; q + 1 < sz; ++q, lst = node[i][p], ++p) {
            // int il = lst + 1, ir = node[i][q] - 1;
            // lst + 1 , node[i][p], node[i][q] + 1, node[i][q + 1] - 1
            if (node[i][q] > node[i][q + 1] - 1)continue;
            opt.push_back({lst + 1, node[i][q], node[i][q + 1] - 1, 1});
            opt.push_back({node[i][p] + 1, node[i][q], node[i][q + 1] - 1, -1});
        }
    }
    // int ans = 0;
    sort(opt.begin(), opt.end());
    auto idx = opt.begin();
    debug(opt);
    irep(i, 1, n) {
        while (idx != opt.end() && (*idx)[0] == i) {
            auto [tim, l, r, v] = *idx;
            add(1, v, 1, n, l, r);
            debug(v, l, r);
            ++idx;
        }
        debug(_sg[1].sum);
        // cerr << _sg[1].sum << endl;
        ans += (n - i + 1) - _sg[1].sum;
    }
    cout << ans;
}


void solve() {
}

signed main() {
    IOS;
    init();
    // debug(1);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}