algorithm - 指定されたインデックスの数値よりも小さい配列のインデックス番号で最も近いものを見つける

Question

これはアルゴリズムの最適化問題です。

整数配列があり、そのような要素のインデックスを含むA配列を構築したい( )BB[i]jA[j]B[i] = j

1. j > i
2. A[j] < A[i]
3. j is minimum of all possible j's.

たとえば、次の場合A:

   A = [1,5,6,4,3,1,2]

次にBなります（0からのインデックス）

   B = [-1,3,3,4,5,-1,-1]

B[0] = -11よりも大きいインデックスを持つ よりも小さい数字は存在しないため0です。 B[1] = 3なぜなら、は、より小さい数を含む、でA[3]インデックスを作成する最も右に近い要素だからです。などなど。1AA[1]=5

O(n*log(n))二分探索木を使用した複雑なソリューションを知っています。O(n)複雑さを高めたり、それが不可能であることを証明するにはどうすればよいですか?