APL, 2 bytes
The “grade up” built-in, applied twice. Works if indexing starts at 0, which isn’t the default for all flavors of APL.
Why does this work?
⍋x returns a list of indices that would stably sort
x. For example:
x ← 4 4 0 1 1 2 0 1 ⍋x 2 6 3 4 7 5 0 1
because if you take element
3… you get a stably sorted list:
x[⍋x] 0 0 1 1 1 2 4 4
But the index list that answers this question is subtly different: first we want the index of the smallest element, then the second smallest, etc. — again, keeping the original order.
If we look at
⍋x, though, we see it can give us this list easily: the position of a
⍋x tells us where the smallest element would end up after sorting, and the position of a
⍋x tells us where the second smallest element would end up, etc.
But we know
⍋x contains exactly the numbers [0, 1… n−1]. If we grade it again, we’ll just get the index of
⍋x, then the index of
⍋x, etc., which is precisely what we’re interested in.
So the answer is