提示: 欢迎访问OurACM平台。
Problem 1845 Look Up

Accept: 229    Submit: 661
Time Limit: 1000 mSec    Memory Limit : 32768 KB

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

    Sample Output

    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