与えられた条件は「$A_i < A_j < A_k$ を満たす $(i,j,k)$ の組の個数を求めよ」と読み替えることができます。

$j$ を全探索します。このとき、$i,k$ は独立に選ぶことができます。$i$ の選択肢の個数は $A$ に含まれる $A_j$ より小さな要素の個数、$k$ の選択肢の個数は $A$ に含まれる $A_j$ より大きな要素の個数となります。したがって、「$A$ に $x$ 未満の要素が何個あるか？」を表す配列を予め用意しておくことで、この問題を $O(N+\max A)$ で解くことができます。

実装例(Python)