defmodule MaxCounters do
  def max_counters(n, a) do
    condition = n + 1

    {counters, _max_counter, last_update} =
      Enum.reduce(a, {%{}, 0, 0}, fn v, {counters, max_counter, last_update} ->
        cond do
          v <= n ->
            index = v - 1
            updated = max(Map.get(counters, index, 0), last_update) + 1
            {Map.put(counters, index, updated), max(max_counter, updated), last_update}

          v == condition ->
            {counters, max_counter, max_counter}

          true ->
            {counters, max_counter, last_update}
        end
      end)

    0..(n - 1)
    |> Enum.map(fn i -> max(Map.get(counters, i, 0), last_update) end)
  end
end

-module(max_counters).
-export([max_counters/2]).

max_counters(N, A) ->
    Condition = N + 1,
    {CountersMap, _MaxCounter, LastUpdate} = lists:foldl(fun(V, {Map, MaxC, Last}) ->
        case V of
            Condition ->
                {Map, MaxC, MaxC};
            _ when V =< N ->
                Index = V - 1,
                NewVal = max(maps:get(Index, Map, 0), Last) + 1,
                {maps:put(Index, NewVal, Map), max(MaxC, NewVal), Last};
            _ ->
                {Map, MaxC, Last}
        end
    end, {#{}, 0, 0}, A),
    [max(maps:get(I, CountersMap, 0), LastUpdate) || I <- lists:seq(0, N - 1)].

func maxCounters(n int, a []int) []int {
	counters := make([]int, n)
	maxCounter := 0
	lastUpdate := 0
	condition := n + 1

	for _, v := range a {
		if v <= n {
			index := v - 1
			if counters[index] < lastUpdate {
				counters[index] = lastUpdate // should already be maxed
			}
			counters[index]++
			if counters[index] > maxCounter {
				maxCounter = counters[index]
			}
		}
		if v == condition {
			lastUpdate = maxCounter
		}
	}

	// apply all max operations to avoid O(M*N) complexity
	for k, v := range counters {
		if v < lastUpdate {
			counters[k] = lastUpdate
		}
	}

	return counters
}

import Control.Monad (forM_, when)
import Control.Monad.ST (ST, runST)
import Data.Array.ST (STArray, getElems, newArray, readArray, writeArray)
import Data.STRef (newSTRef, readSTRef, writeSTRef)

maxCounters :: Int -> [Int] -> [Int]
maxCounters n a = runST $ do
  counters <- newArray (0, n - 1) 0 :: ST s (STArray s Int Int)
  maxRef   <- newSTRef 0
  lastRef  <- newSTRef 0
  forM_ a $ \v ->
    if v <= n
      then do
        let idx = v - 1
        lastUpdate <- readSTRef lastRef
        cur        <- readArray counters idx
        let cur' = max cur lastUpdate + 1
        writeArray counters idx cur'
        maxC <- readSTRef maxRef
        when (cur' > maxC) (writeSTRef maxRef cur')
      else
        when (v == n + 1) (readSTRef maxRef >>= writeSTRef lastRef)
  lastUpdate <- readSTRef lastRef
  finalCounters <- getElems counters
  return (map (max lastUpdate) finalCounters)

public class Solution {
    public static int[] maxCounters(int n, int[] a) {
        int[] counters = new int[n];
        int maxCounter = 0;
        int lastUpdate = 0;
        int condition = n + 1;

        for (int v : a) {
            if (v <= n) {
                int index = v - 1;
                if (counters[index] < lastUpdate) {
                    counters[index] = lastUpdate;
                }
                counters[index]++;
                maxCounter = Math.max(counters[index], maxCounter);
            }
            if (v == condition) {
                lastUpdate = maxCounter;
            }
        }

        for (int k = 0; k < counters.length; k++) {
            if (counters[k] < lastUpdate) {
                counters[k] = lastUpdate;
            }
        }

        return counters;
    }
}

(defun max-counters (n a)
  (let ((counters (make-array n :initial-element 0))
        (max-counter 0)
        (last-update 0)
        (condition (1+ n)))
    (dolist (v a)
      (when (<= v n)
        (let ((index (1- v)))
          (when (< (aref counters index) last-update)
            (setf (aref counters index) last-update))
          (incf (aref counters index))
          (setf max-counter (max max-counter (aref counters index)))))
      (when (= v condition)
        (setf last-update max-counter)))
    (dotimes (k n)
      (when (< (aref counters k) last-update)
        (setf (aref counters k) last-update)))
    (coerce counters 'list)))

function maxCounters(int $n, array $a): array
{
    $counters   = array_fill(0, $n, 0);
    $maxCounter = 0;
    $lastUpdate = 0;
    $condition  = $n + 1;

    foreach ($a as $v) {
        if ($v <= $n) {
            $index = $v - 1;
            if ($counters[$index] < $lastUpdate) {
                $counters[$index] = $lastUpdate; // should already be maxed
            }
            $counters[$index]++;
            $maxCounter = $counters[$index] > $maxCounter ? $counters[$index] : $maxCounter;
        }
        if ($v === $condition) {
            $lastUpdate = $maxCounter;
        }
    }

    // apply all max operations to avoid O(M*N) complexity
    foreach ($counters as $k => $v) {
        if ($v < $lastUpdate) {
            $counters[$k] = $lastUpdate;
        }
    }

    return $counters;
}

def max_counters(n: int, a: list[int]) -> list[int]:
    counters = [0] * n
    max_counter = 0
    last_update = 0
    condition = n + 1

    for v in a:
        if v <= n:
            index = v - 1
            if counters[index] < last_update:
                counters[index] = last_update
            counters[index] += 1
            max_counter = max(counters[index], max_counter)
        if v == condition:
            last_update = max_counter

    for k, v in enumerate(counters):
        if v < last_update:
            counters[k] = last_update

    return counters

fn max_counters(n: i64, a: &[i64]) -> Vec<i64> {
    let mut counters = vec![0i64; n as usize];
    let mut max_counter = 0i64;
    let mut last_update = 0i64;
    let condition = n + 1;

    for &v in a {
        if v <= n {
            let index = (v - 1) as usize;
            if counters[index] < last_update {
                counters[index] = last_update;
            }
            counters[index] += 1;
            max_counter = max_counter.max(counters[index]);
        }
        if v == condition {
            last_update = max_counter;
        }
    }

    for c in counters.iter_mut() {
        if *c < last_update {
            *c = last_update;
        }
    }

    counters
}

function maxCounters(n: number, a: number[]): number[] {
  const counters: number[] = new Array(n).fill(0);
  let maxCounter = 0;
  let lastUpdate = 0;
  const condition = n + 1;

  for (const v of a) {
    if (v <= n) {
      const index = v - 1;
      if (counters[index] < lastUpdate) {
        counters[index] = lastUpdate;
      }
      counters[index]++;
      maxCounter = counters[index] > maxCounter ? counters[index] : maxCounter;
    }
    if (v === condition) {
      lastUpdate = maxCounter;
    }
  }

  return counters.map((v) => (v < lastUpdate ? lastUpdate : v));
}