#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>

using i64 = long long;

struct Node{
	int l, r, mark, cnt;

	Node(): l(0), r(0), mark(0), cnt(0) {}
};

vector<Node> node;

void build(int l, int r, int idx = 1){
	node[idx].l = l, node[idx].r = r;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(l, mid, idx << 1);
	build(mid + 1, r, idx << 1 | 1);
	return;
}

void pushup(int idx){
	if(node[idx].mark != 0){
		node[idx].cnt = node[idx].r - node[idx].l + 1;
	}
	else{
		node[idx].cnt = node[idx << 1].cnt + node[idx << 1 | 1].cnt;
	}
	return;
}

void pushdown(int idx){
	if(node[idx].mark == 0) return;
	int idl = idx << 1, idr = idx << 1 | 1;
	node[idl].mark += node[idx].mark, node[idr].mark += node[idx].mark;
}

void update(int l, int r, int v, int idx = 1){
	int tl = node[idx].l, tr = node[idx].r;
	if(l <= tl && tr <= r){
		node[idx].mark += v;
		if(tl == tr){
			if(node[idx].mark == 0) node[idx].cnt = 0;
			else node[idx].cnt = 1;
		}
		else{
			pushup(idx);
		}
		return;
	}
	if(tr < l || r < tl) return;
	//pushdown(idx);
	int mid = (tl + tr) >> 1;
	if(mid >= l) update(l, r, v, idx << 1);
	if(mid < r) update(l, r, v, idx << 1 | 1);
	pushup(idx);
	return;
}

int query(int l, int r, int idx = 1){
	int tl = node[idx].l, tr = node[idx].r;
	if(l <= tl && tr <= r) return node[idx].cnt;
	int ans = 0;
	if(tr < l || r < tl) return 0;
	//pushdown(idx);
	int mid = (tl + tr) >> 1;
	if(mid >= l) ans += query(l, r, idx << 1);
	if(mid < r) ans += query(l, r, idx << 1 | 1);
	if(node[idx].mark != 0) ans = min(min(tr - tl + 1, r - l + 1), min(tr - l + 1, r - tl + 1));
	return ans;
}

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

	int n, k;
	cin >> n >> k;

    node.resize(n << 2 | 1);
    build(1, n);

	vector<int> a(n + 1);
	for(int i = 1; i <= n; ++i) cin >> a[i];

	int mn = *max_element(a.begin() + 1, a.end());
	vector<int> last(n + 1), lasta(mn + 1);

	for(int i = 1; i <= n; ++i){
		last[i] = lasta[a[i]];
		lasta[a[i]] = i;
	}

	vector<int> lastk(n + 1);

	for(int i = 1; i <= n; ++i){
		if(lasta[i] == 0) continue;
		int p = lasta[i];
		for(int j = 0; j < k - 1 && p != 0; ++j){
			p = last[p];
		}

		int tp = lasta[i];
		while(p != 0){
			lastk[tp] = p;
			p = last[p];
			tp = last[tp];
		}
	}

	i64 ans = 0;
	for(int i = 1; i <= n; ++i){
		if(lastk[i] != 0){
			int p = last[i];
			if(lastk[p] != 0) update(lastk[last[p]] + 1, lastk[p], -1);
			update(lastk[p] + 1, lastk[i], 1);
			//cout << i << " " << lastk[p] + 1 << " " << lastk[i] << "\n";
		}
		//cout << i - query(1, i) << "\n";
		ans += i - query(1, i);
	}

	cout << ans << "\n";

	return 0;
}