\(j\) を探すにあたって、\(j<k<i\) かつ \(A_j<A_k\) となる \(k\) が存在する \(j\) を考慮する必要はありません。つまり、問題を解くために必要なのは「\(i\) から遡って先頭の方へ行くとき、大きくなっていく要素」だけです。

例

7 3 9 5 4 6 1 2       <-- 後ろから遡って見る
    ^     ^   ^       (9,6,2) だけが重要

そのような要素をスタックで管理すると、どの要素もスタックから出し入れする回数は高々1回であることから、\(O(N)\) でこの問題を解くことができます。

実装上は、列の先頭に十分大きな値を番兵として配置すると簡単です。

実装例(Python)

N=int(input())
A=list(map(int,input().split()))

S=[(10**9,-1)]

for i,a in enumerate(A,1):
  while S[-1][0]<a:
    S.pop()
  print(S[-1][1])
  S.append((a,i))