#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 1e6 + 10,INF = 1e9;
int T,n,k;
int a[N];
vector<int> pos[N];
struct Node
{
    int l,r;
    int cnt,mn,add;
}tr[N * 4];

void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn,tr[u << 1 | 1].mn);
    tr[u].cnt = 0;
    if(tr[u].mn == tr[u << 1].mn) tr[u].cnt += tr[u << 1].cnt;
    if(tr[u].mn == tr[u << 1 | 1].mn) tr[u].cnt += tr[u << 1 | 1].cnt;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1],&right = tr[u << 1 | 1];
    if(root.l == root.r) return ;
    if(root.add)
    {
        left.add += root.add;
        left.mn += root.add;
        right.add += right.add;
        right.mn += root.add;
        root.add = 0;
    }
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        tr[u] = {l,r,1,0,0};
        return ;
    }
    else{
        tr[u] = {l,r,r - l + 1,0,0};
        int mid = (l + r) >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}

void modify(int u,int l,int r,int d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].mn += d;
        tr[u].add += d;
    }
    else{
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) modify(u << 1,l,r,d);
        if(r > mid) modify(u << 1 | 1,l,r,d);
        pushup(u);
    }
}

array<int,2> query(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return {tr[u].mn,tr[u].cnt};
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int mn = INF,cnt = 0;
    array<int,2> tmp = {INF,0};
    if(l <= mid) tmp = query(u << 1,l,r);
    mn = min(mn,tmp[0]),cnt = tmp[1];
    tmp = {INF,0};
    if(r > mid) tmp = query(u << 1 | 1,l,r);
    if(tmp[0] > mn)
    {
        return {mn,cnt};
    }
    else if(tmp[0] < mn) return tmp;
    else
    {
        return {mn,tmp[1] + cnt};
    }
}

void change(vector<int>& tmp,int x)
{
    int pos = lower_bound(tmp.begin(),tmp.end(),x) - tmp.begin();
    if(pos == k)
    {
        modify(1,tmp[pos - k] + 1,tmp[pos - k + 1],1);
    }
    if(pos > k)
    {
        modify(1,tmp[pos - k - 1] + 1,tmp[pos - k],-1);
        modify(1,tmp[pos - k] + 1,tmp[pos - k + 1],1);
    }
}

void solve()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++) 
    {
        cin >> a[i];
        if(pos[a[i]].empty()) pos[a[i]].push_back(0);
        pos[a[i]].push_back(i);
    }
    build(1,1,n);
    int ans = 0;
    for(int i = 1;i <= n;i++)
    {
//         int p = lower_bound(pos[a[i]].begin(),pos[a[i]].end(),i) - pos[a[i]].begin();
//         if(p == k - 1)
//         {
//             modify(1,1,pos[a[i]][0],1);
//         }
//         else if(p == k)
//         {
//             modify(1,1,pos[a[i]][0],-1);
//             modify(1,pos[a[i]][0] + 1,pos[a[i]][1],1);
//         }
//         else if(p > k)
//         {
//             modify(1,pos[a[i]][p - k - 1] + 1,pos[a[i]][p - k],-1);
//             modify(1,pos[a[i]][p - k] + 1,pos[a[i]][p - k + 1],1);
//         }
        change(pos[a[i]],i);
        array<int,2> temp = query(1,1,i);
        if(!temp[0]) ans += i - temp[1];
        else ans += i;
    }
    cout << n * (n + 1) / 2 - ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    T = 1;
    while(T--)
    {
        solve();
    }
}