static int[] MaxCounters(int n, int[] a)
{
    var counters = new int[n];
    var maxCounter = 0;
    var lastUpdate = 0;
    var condition = n + 1;

    foreach (var v in a)
    {
        if (v <= n)
        {
            var index = v - 1;
            if (counters[index] < lastUpdate)
            {
                counters[index] = lastUpdate;
            }
            counters[index]++;
            maxCounter = Math.Max(counters[index], maxCounter);
        }
        if (v == condition)
        {
            lastUpdate = maxCounter;
        }
    }

    // apply all max operations to avoid O(M*N) complexity
    for (int k = 0; k < counters.Length; k++)
    {
        if (counters[k] < lastUpdate)
        {
            counters[k] = lastUpdate;
        }
    }

    return counters;
}