#include <bits/stdc++.h>

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

struct segment_tree
{
    struct node
    {
        bool cle;
        ll x, add, p, sh;

        inline void build()
        {
            cle = 0;
            x = 0;
            clean_lazy();
        }

        inline bool has_lazy()
        {
            return add > 0 || p > 0 || sh > 0 || cle;
        }

        inline void clean_lazy()
        {
            cle = 0;
            add = 0, p = 0, sh = 0;
        }
    };

    struct update_info
    {
        ll x;
        bool pa;
    };

private:

    // merge l and r into u
    inline void merge(node &u, node &l, node &r)
    {
        u.x = l.x + r.x;
    }

    // propagate lazy of p into u
    inline void prop(node &p, node &u, int szu, int szl)
    {
        if (p.cle)
        {
            u.x = 0;
            u.clean_lazy();
            u.cle = 1;
        }
        u.x += p.add * szu;
        ll fi = p.p + szl * p.sh;
        u.x += fi * szu + ((ll)szu-1) * szu / 2 * p.sh;
        u.add += p.add;
        u.p += fi;
        u.sh += p.sh;
    }

    // update u with x
    inline void apply(node &u, update_info &x, int b, int e, int lo, int hi)
    {
        if (!x.pa)
        {
            u.x += (e-b) * x.x;
            u.add += x.x;
        }
        else
        {
            ll fi = 1 + b-lo;
            ll to = fi + e-b-1;
            u.x += to * (to+1) / 2 - (fi-1) * fi / 2;
            u.p += fi;
            ++u.sh;
        }
    }

    inline void push(node &u, int b, int e, int m)
    {
        if (u.has_lazy())
        {
            prop(u, st[id(b, m)], m-b, 0);
            prop(u, st[id(m, e)], e-m, m-b);
            u.clean_lazy();
        }
    }

    inline int id(int b, int e) { return (b+e-1) | (b!=e-1); }

    void build(int b, int e)
    {
        node &cur = st[id(b, e)];

        if (b+1 == e)
        {
            cur.build();
            return;
        }

        int m = (b+e+1)>>1;
        build(b, m);
        build(m, e);
        merge(cur, st[id(b, m)], st[id(m, e)]);
    }

    void update(int b, int e, int lo, int hi, update_info &x)
    {
        node &cur = st[id(b, e)];

        if (lo <= b && e <= hi)
        {
            apply(cur, x, b, e, lo, hi);
            return;
        }

        int m  = (b+e+1)>>1;
        push(cur, b, e, m);

        if (lo < m) update(b, m, lo, hi, x);
        if (m < hi) update(m, e, lo, hi, x);
        merge(cur, st[id(b, m)], st[id(m, e)]);
    }

    ll query(int b, int e, int lo, int hi)
    {
        node &cur = st[id(b, e)];

        if (lo <= b && e <= hi)
            return cur.x;

        int m = (b+e+1)>>1;
        push(cur, b, e, m);

        ll ret = 0;
        if (lo < m) ret += query(b, m, lo, hi);
        if (m < hi) ret += query(m, e, lo, hi);
        return ret;
    }

    int n;
    vector<node> st;

public:
    void build()
    {
        build(0, n);
    }

    void update(int lo, int hi, update_info x)
    {
        //debug("update", lo, hi, x.x, x.pa);
        update(0, n, lo, hi+1, x);
    }

    ll query(int lo, int hi)
    {
        //debug("query", lo, hi);
        return query(0, n, lo, hi+1);
    }

    void clear()
    {
        st[id(0, n)].x = 0;
        st[id(0, n)].clean_lazy();
        st[id(0, n)].cle = true;
    }

    segment_tree(int n) : n(n), st(2*n) {}
};

ll brute(vector<int> a, int k)
{
    ll r = 0;
    int n = a.size();
    for (int i = 0; i < n; ++i)
    {
        int s = 0;
        for (int j = i; j < n; ++j)
        {
            s += (a[j] == k) ? +1 : -1;
            r += s > 0;
        }
    }
    return r;
}

int main()
{
    #ifdef DGC
        freopen("a.in", "r", stdin);
        //freopen("b.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &i : a) cin >> i;

    const int N = 1e6 + 5, L = 2*N + 5;
    segment_tree st(2*N + 10);
    st.build();

    auto solve = [&](vector<int> v)
    {
        //debug("solve", v);
        st.clear();
        st.update(N, L, { 1, false });
        ll ret = 0;
        int cur = 0;
        for (auto i : v)
        {
            if (i < 0)
            {
                ret += st.query(N + cur+i-1, N + cur-2);
                st.update(N + cur+i, N + cur-1, { 1, true });
                st.update(N + cur, L, { -i, false });
                cur += i;
            }
            else
            {
                ++cur;
                ret += st.query(N + cur-1, N + cur-1);
                //debug(cur, ret);
                st.update(N + cur, L, { 1, false });
            }
        }
        return ret;
    };

    vector<vector<int>> pos(k);
    for (int i = 0; i < n; ++i)
        pos[a[i]].push_back(i);

    vector<ll> ans(k);
    for (auto &p : pos)
    {
        vector<int> aux;
        int sz = p.size();
        if (!sz) continue;
        for (auto i : p)
        {
            if (i > 0 && (aux.empty() || aux.back()+1 != i))
            {
                int val = i - (aux.empty() ? 0 : (aux.back()+1));
                aux.push_back(-val);
            }
            aux.push_back(i);
        }
        if (aux.back() != n-1)
            aux.push_back(-(n-1-aux.back()));
        ans[&p-&pos[0]] = solve(aux);
    }

    //cout << clock() * 1000 / CLOCKS_PER_SEC << endl; return 0;
    for (auto &i : ans)
        cout << i << "\n";

    /*cout << endl;
    for (int i = 0; i < k; ++i)
        cout << brute(a, i) << "\n";*/

    return 0;
}