﻿ Fuzhou University OnlineJudge ﻿
Problem 1845 Look Up

## Problem Description

N (1 <= N <= 100,000) monkeys in the mountains, conveniently numbered 1..N, are once again standing in a row. Monkey i has height Hi (1 <= Hi <= 1,000,000).

Each monkey is looking to his left toward those with higher index numbers. We say that monkey i "looks up" to monkey j if i < j and Hi < Hj. For each monkey i, we would like to know the index of the first monkey in line looked up to by monkey i.

## Input

Input consists of several testcases. The format of each case as follow:

• Line 1: A single integer: N
• Lines 2..N+1: Line i+1 contains the single integer: Hi
• ## Output

For each testcase, output N lines. Line i contains a single integer representing the smallest index of a monkey up to which monkey i looks. If no such monkey exists, print 0.

## Sample Input

6 3 2 6 1 1 2

3 3 0 6 6 0

## Hint

Monkey 1 and 2 both look up to monkey 3; monkey 4 and 5 both look up to monkey 6; and monkey 3 and 6 do not look up to any monkey.

## Source

Funny Programming Contest -- OSUM

Submit  Back  Status  Discuss
﻿