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

int n, K;
vector<int> a;   // a[1..n]

// Sub 1: vet can. Voi moi dau trai l, mo rong r ve phai, duy tri eq[j] = so gia tri xuat hien dung j lan.
// Doan [l..r] tot khi eq[1..K] deu > 0. O(n^2 * K) nhung moi buoc chi O(K). Dung khi n <= 5000
void sub1() {
    long long ans = 0;
    vector<int> cnt(n + 1, 0), eq(K + 2, 0);
    for (int l = 1; l <= n; l++) {
        fill(cnt.begin(), cnt.end(), 0);
        fill(eq.begin(), eq.end(), 0);
        for (int r = l; r <= n; r++) {
            int v = a[r], c = cnt[v];
            if (c >= 1 && c <= K) eq[c]--;       // gia tri v roi khoi so dem cu
            cnt[v]++;
            c++;
            if (c <= K) eq[c]++;                 // gia tri v vao so dem moi
            bool ok = true;
            for (int j = 1; j <= K; j++) if (eq[j] == 0) { ok = false; break; }
            if (ok) ans++;
        }
    }
    cout << ans << "\n";
}

// Sub 2 (day du): dem theo dau phai r, voi moi dau trai l co "good" neu voi moi j in [1..K] co mot gia tri
// xuat hien dung j lan trong [l..r]. Voi moi j, cov_j(l) = so gia tri co dung j lan trong [l..r].
// Gia tri v co dung j lan trong [l..r] khi l thuoc (q_{m-j}, q_{m-j+1}], voi q la vi tri xuat hien cua v.
// Dung cay doan (min, dem min) cho moi tap con S cua {1..K} luu W_S(l) = tong cov_j(l) voi j trong S.
// Inclusion-exclusion: so l tot = sum_S (-1)^{|S|} #{l : W_S(l) = 0}. O(n * 2^K * K * log n). Dung cho moi n
struct Seg {
    int n;
    vector<int> mn, cn, lz;
    void init(int sz) {
        n = sz;
        mn.assign(4 * n + 4, 0); cn.assign(4 * n + 4, 0); lz.assign(4 * n + 4, 0);
        build(1, 1, n);
    }
    void build(int x, int l, int r) {
        cn[x] = r - l + 1;
        if (l == r) return;
        int m = (l + r) / 2;
        build(2 * x, l, m); build(2 * x + 1, m + 1, r);
    }
    void apply(int x, int v) { mn[x] += v; lz[x] += v; }
    void push(int x) {
        if (lz[x]) { apply(2 * x, lz[x]); apply(2 * x + 1, lz[x]); lz[x] = 0; }
    }
    void pull(int x) {
        int L = 2 * x, R = 2 * x + 1;
        if (mn[L] < mn[R]) { mn[x] = mn[L]; cn[x] = cn[L]; }
        else if (mn[L] > mn[R]) { mn[x] = mn[R]; cn[x] = cn[R]; }
        else { mn[x] = mn[L]; cn[x] = cn[L] + cn[R]; }
    }
    void upd(int x, int l, int r, int ql, int qr, int v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(x, v); return; }
        push(x);
        int m = (l + r) / 2;
        upd(2 * x, l, m, ql, qr, v); upd(2 * x + 1, m + 1, r, ql, qr, v);
        pull(x);
    }
    pair<int, int> qry(int x, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return {INT_MAX, 0};
        if (ql <= l && r <= qr) return {mn[x], cn[x]};
        push(x);
        int m = (l + r) / 2;
        auto L = qry(2 * x, l, m, ql, qr), R = qry(2 * x + 1, m + 1, r, ql, qr);
        if (L.first < R.first) return L;
        if (L.first > R.first) return R;
        return {L.first, L.second + R.second};
    }
    // so vi tri l trong [1..r] co W(l) = 0 (W >= 0 nen min = 0 la du)
    int zeros(int r) {
        auto p = qry(1, 1, n, 1, r);
        return p.first == 0 ? p.second : 0;
    }
};

void sub2() {
    int full = 1 << K;                    // tap con S cua {1..K} duoc ma hoa bit (j-1)
    vector<Seg> seg(full);
    for (int m = 1; m < full; m++) seg[m].init(n);
    vector<vector<int>> pos(n + 1);       // vi tri xuat hien cua moi gia tri
    // them (sign=+1) hoac bo (sign=-1) dong gop cua gia tri v khi no co m lan xuat hien
    auto contrib = [&](int v, int m, int sign) {
        for (int j = 1; j <= min(K, m); j++) {
            int hi = pos[v][m - j];                              // q_{m-j+1}
            int lo = (m - j - 1 >= 0) ? pos[v][m - j - 1] : 0;   // q_{m-j}
            if (lo + 1 > hi) continue;
            for (int mask = 1; mask < full; mask++)
                if ((mask >> (j - 1)) & 1) seg[mask].upd(1, 1, n, lo + 1, hi, sign);
        }
    };
    long long total = 0;
    for (int r = 1; r <= n; r++) {
        int v = a[r];
        int mo = pos[v].size();
        if (mo > 0) contrib(v, mo, -1);
        pos[v].push_back(r);
        contrib(v, mo + 1, +1);
        long long good = r;               // S rong, dau +
        for (int mask = 1; mask < full; mask++) {
            long long z = seg[mask].zeros(r);
            if (__builtin_popcount(mask) & 1) good -= z; else good += z;
        }
        total += good;
    }
    cout << total << "\n";
}

int main() {
    freopen("COUNT.INP", "r", stdin);
    freopen("COUNT.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n <= 5000) sub1();
    else sub2();
    return 0;
}