#include <bits/stdc++.h>

using namespace std;

int n, k, a[100005], prv[100005];

struct sgtn
{
    int mnm = 0, lazy = 0, cntmin;
};

sgtn aint[20][400005];

void build(int nod, int l, int r)
{
    for (int i = 1; i < (1 << k); i++)
        aint[i][nod].mnm = aint[i][nod].lazy = 0, aint[i][nod].cntmin = r - l + 1;
    if (l != r)
    {
        int mij = (l + r) / 2;
        build(2 * nod, l, mij);
        build(2 * nod + 1, mij + 1, r);
    }
}

void prop(int mask, int nod, int l, int r)
{
    if (l != r)
    {
        int lz = aint[mask][nod].lazy;
        aint[mask][2 * nod].mnm += lz;
        aint[mask][2 * nod].lazy += lz;
        aint[mask][2 * nod + 1].mnm += lz;
        aint[mask][2 * nod + 1].lazy += lz;
    }
    aint[mask][nod].lazy = 0;
}

void update(int mask, int nod, int l, int r, int st, int dr, int val)
{
    //if (nod == 1)
    //    cout << mask << ' ' << st << ' ' << dr << ' ' << val << endl;
    prop(mask, nod, l, r);
    if (r < st or dr < l)
        return;
    if (st <= l and r <= dr)
    {
        aint[mask][nod].mnm += val;
        aint[mask][nod].lazy += val;
        return;
    }
    int mij = (l + r) / 2;
    update(mask, 2 * nod, l, mij, st, dr, val);
    update(mask, 2 * nod + 1, mij + 1, r, st, dr, val);
    if (aint[mask][2 * nod].mnm < aint[mask][2 * nod + 1].mnm)
        aint[mask][nod].mnm = aint[mask][2 * nod].mnm, aint[mask][nod].cntmin = aint[mask][2 * nod].cntmin;
    else if (aint[mask][2 * nod].mnm > aint[mask][2 * nod + 1].mnm)
        aint[mask][nod].mnm = aint[mask][2 * nod + 1].mnm, aint[mask][nod].cntmin = aint[mask][2 * nod + 1].cntmin;
    else
        aint[mask][nod].mnm = aint[mask][2 * nod].mnm, aint[mask][nod].cntmin = aint[mask][2 * nod].cntmin + aint[mask][2 * nod + 1].cntmin;
}

pair<int,int> query(int mask, int nod, int l, int r, int st, int dr)
{
    prop(mask, nod, l, r);
    if (r < st or dr < l)
        return {1e9, 0};
    else if (st <= l and r <= dr)
        return {aint[mask][nod].mnm, aint[mask][nod].cntmin};
    int mij = (l + r) / 2;
    pair<int, int> p1 = query(mask, 2 * nod, l, mij, st, dr);
    pair<int, int> p2 = query(mask, 2 * nod + 1, mij + 1, r, st, dr);
    if (p1.first < p2.first)
        return p1;
    else if (p1.first > p2.first)
        return p2;
    else
        return {p1.first, p1.second + p2.second};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    map<int, int> prea;
    for (int i = 1; i <= n; i++)
    {
        prv[i] = prea[a[i]];
        prea[a[i]] = i;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            int x = i;
            for (int q = 1; q < j; q++)
                x = prv[x];
            if (x == 0)
                continue;
            int xx = x;
            for (int mask = 1; mask < (1 << k); mask++)
            {
                x = xx;
                if (mask & (1 << (j - 1)))
                {
                    update(mask, 1, 1, n, prv[x] + 1, x, 1);
                    x = prv[x];
                    if (x != 0)
                        update(mask, 1, 1, n, prv[x] + 1, x, -1);
                }
            }
        }
        int adg = i;
        for (int mask = 1; mask < (1 << k); mask++)
        {
            pair<int, int> pp = query(mask, 1, 1, n, 1, i);
            int df = 0;
            if (pp.first == 0)
                df = pp.second;
            //if (i == 1)
                //cout << mask << ' ' << df << endl;
            if ((int)(__builtin_popcount(mask)) % 2 == 1)
                df = -df;
            adg += df;
        }
        //cout << adg << endl;
        ans += adg;
    }
    cout << ans;
    return 0;
}