#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 lazy_container
    {
        bool clear;
        ll first, dif;

        inline void operator~() // clean lazy
        {
            *this = lazy_container();
        }

        inline bool operator()() // has lazy
        {
            return first > 0 || dif > 0 || clear;
        }

        lazy_container() : clear(0), first(0), dif(0) {}
        lazy_container(bool clear, ll first, ll dif) : clear(clear), first(first), dif(dif) {}
    };

    struct node
    {
        ll x;
        lazy_container lazy;

        node() : x(0) {}

        inline void apply(int l, int r, const lazy_container &p, int szl) // propagate lazy of p
        {
            if (p.clear)
            {
                x = 0;
                ~lazy;
                lazy.clear = 1;
            }
            int sz = r-l;
            ll first = p.first + szl * p.dif;
            x += first * sz + ((ll)sz-1) * sz / 2 * p.dif;
            lazy.first += first;
            lazy.dif += p.dif;
        }
    };

private:
    inline node merge(const node &l, const node &r) const // merge l and r
    {
        node ret;
        ret.x = l.x + r.x;
        return ret;
    }

    inline void push(int x, int b, int e, int m)
    {
        if (st[x].lazy())
        {
            st[x + 1].apply(b, m, st[x].lazy, 0);
            st[x + ((m - b) << 1)].apply(m, e, st[x].lazy, m-b);
            ~st[x].lazy;
        }
    }

    void update(int x, int b, int e)
    {
        if (lo <= b && e <= hi)
        {
            st[x].apply(b, e, lazy, b-lo);
            return;
        }

        int m = (b + e) >> 1;
        int y = x + ((m - b) << 1);
        push(x, b, e, m);

        if (lo < m) update(x + 1, b, m);
        if (m < hi) update(y, m, e);
        st[x] = merge(st[x + 1], st[y]);
    }

    node query(int x, int b, int e)
    {
        if (lo <= b && e <= hi)
            return st[x];

        int m = (b + e) >> 1;
        int y = x + ((m - b) << 1);
        push(x, b, e, m);

        if (m >= hi) return query(x + 1, b, m);
        if (m <= lo) return query(y, m, e);
        return merge(query(x + 1, b, m), query(y, m, e));
    }

    lazy_container lazy;
    int n, lo, hi;
    vector<node> st;

public:
    void update(int l, int r, const lazy_container &x)
    {
        lo = l, hi = r+1, lazy = x;
        update(0, 0, n);
    }

    node query(int l, int r)
    {
        lo = l, hi = r+1;
        return query(0, 0, n);
    }

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

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(L + 5);

    auto solve = [&](const vector<int> &v)
    {
        if (v.empty()) return 0LL;
        st.update(0, L + 5, { 1, 0, 0 });
        st.update(N, L, { 0, 1, 0 });
        ll ret = 0;
        int cur = 0;
        for (auto i : v)
        {
            if (i < 0)
            {
                ret += st.query(N + cur+i-1, N + cur-2).x;
                st.update(N + cur+i, N + cur-1, { 0, 1, 1 });
                st.update(N + cur, L, { 0, -i, 0 });
                cur += i;
            }
            else
            {
                ++cur;
                ret += st.query(N + cur-1, N + cur-1).x;
                st.update(N + cur, L, { 0, 1, 0 });
            }
        }
        return ret;
    };

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

    for (auto &p : pos)
    {
        vector<int> aux;
        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.empty() && aux.back() != n-1)
            aux.push_back(-(n-1-aux.back()));
        cout << solve(aux) << "\n";
    }

    return 0;
}