Hi everyone,

Given a sequence of n numbers, {a1; a2; ; an}, for each element
, 1 ≤ i ≤ n, nd the index of the rightmost element inside {a1; a2; ; ai1} whose value is
strictly larger than ai
. If no element is larger than ai then output 0. In other words, for
each i
pi = max{j|0 ≤ j < i; aj > ai};
in which assume a0 = ∞

O(n) should be the running time.

Please help.