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)