P2947 [USACO09MAR] Look Up S

Farmer John's $N(1 \le N \le 10^5)$ cows, conveniently numbered $1$ to $N$, are once again standing in a row. Cow $i$ has height $H_i(1 \le H_i \le 10^6)$. Each cow is looking to her right toward those with higher index numbers. We say that cow $i$ "looks up to" cow $j$ if $i < j$ and $H_i < H_j$. For each cow $i$, FJ would like to know the index of the first cow in line "looked up to" by cow $i$. Note: about $50\%$ of the test data will have $N \le 10^3$.

Line $1$ : A single integer: $N$. Lines $2$ to $N+1$ : Line $i+1$ contains the single integer: $H_i$.

Lines $1$ to $N$: Line $i$ contains a single integer representing the smallest index of a cow up to which cow $i$ looks. If no such cow exists, print $0$.

FJ has six cows of heights $3$, $2$, $6$, $1$, $1$, and $2$. Cows $1$ and $2$ both look up to cow $3$; cows $4$ and $5$ both look up to cow $6$. Cows $3$ and $6$ do not look up to any cow.