Look Up

Interview

Time limit1sMemory limit128 MB

Summary

For each cow, find the smallest index j > i with H_j > H_i, or print 0 if none exists.

Level: Medium4 of 10
Topics: Stack, Array, Implementation
Solved: No attempts yet

Problem

Farmer John's $N$ cows ( $1 \le N \le 100000$ ), conveniently numbered $1 \ldots N$ , are standing in a row. Cow $i$ has height $H_i$ ( $1 \le H_i \le 1000000$ ).

Each cow looks toward the cows with higher index numbers. We say cow $i$ "looks up" to cow $j$ if $i < j$ and $H_i < H_j$ . For each cow $i$ , determine the index of the first cow in the row (the one with the smallest index) that cow $i$ looks up to.

Input

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

Output

Lines 1 to $N$ : line $i$ contains the smallest index of a cow that cow $i$ looks up to. If no such cow exists, print $0$ .

Hint

Cows $1$ and $2$ both look up to cow $3$ ; cows $4$ and $5$ both look up to cow $6$ ; and cows $3$ and $6$ do not look up to any cow.

Examples1

Example 1
Input
```
6
3
2
6
1
1
2
```
Expected output
```
3
3
0
6
6
0
```