#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 50;

struct info_t {
	int mn, cnt;
	info_t() : mn(0), cnt(0) {}
	info_t(int mn, int cnt) : mn(mn), cnt(cnt) {}
} t[N << 2];

info_t operator+(const info_t &lhs, const info_t &rhs) {
	if (lhs.mn < rhs.mn)
		return info_t(lhs.mn, lhs.cnt);
	if (lhs.mn > rhs.mn)
		return info_t(rhs.mn, rhs.cnt);
	return info_t(lhs.mn, lhs.cnt + rhs.cnt);
}

int n, k, a[N], tag[N];
vector<int> p[N];
vector<tuple<int, int, int>> ops[N];

inline int lc(int o) { return o << 1; }
inline int rc(int o) { return o << 1 | 1; }

inline void push_up(int o) {
	t[o] = t[lc(o)] + t[rc(o)];	
}

void maintain(int o, int v) {
	t[o].mn += v;
	tag[o] += v;
}

inline void push_down(int o) {
	if (tag[o] != 0) {
		maintain(lc(o), tag[o]);
		maintain(rc(o), tag[o]);
		tag[o] = 0;
	}
}

void build(int o, int l, int r) {
	if (l == r) {
		t[o] = info_t(0, 1);
	}
	else {
		const int mid = l + r >> 1;
		build(lc(o), l, mid);
		build(rc(o), mid + 1, r);
		push_up(o);
	}
}

void add(int o, int l, int r, int ql, int qr, int v) {
	if (ql <= l && r <= qr) {
		maintain(o, v);
	}
	else {
		const int mid = l + r >> 1;
		push_down(o);
		if (ql <= mid) add(lc(o), l, mid, ql, qr, v);
		if (qr > mid) add(rc(o), mid + 1, r, ql, qr, v);
		push_up(o);
	}
}

info_t query(int o, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr)
		return t[o];
	push_down(o);
	const int mid = l + r >> 1;
	if (qr <= mid)
		return query(lc(o), l, mid, ql, qr);
	if (ql > mid)
		return query(rc(o), mid + 1, r, ql, qr);
	return query(lc(o), l, mid, ql, qr) + query(rc(o), mid + 1, r, ql, qr);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> k;
	build(1, 1, n);
	--k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]].push_back(i);
	}
	for (int i = 1; i <= 1'000'000; ++i)
		if (p[i].size() > k) {
			for (int j = k; j < p[i].size(); ++j) {
				int l1 = (j - k == 0 ? 1 : p[i][j - k - 1]);
				int r1 = p[i][j - k];
				int l2 = p[i][j];
				int r2 = (j + 1 == p[i].size() ? n : p[i][j + 1]);
				ops[l1].emplace_back(l2, r2, 1);
				ops[r1 + 1].emplace_back(l2, r2, -1);
			}
		}
	build(1, 1, n);
	int64_t ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (auto [l, r, v] : ops[i]) {
			add(1, 1, n, l, r, v);
		}
		auto p = query(1, 1, n, 1, n);
		if (p.mn == 0) ans += p.cnt;
		add(1, 1, n, 1, i, 1);
	}
	cout << ans << '\n';
}