AtCoder Count Triplets

atcoder.jp

競技プログラミングはあまり得意ではないですが、たまに挑戦しています。
上の課題については、最初に書いたのが、すべての数字を一つずつチェックする方法です。
以下のようにすぐに書けた(Java)のは良かったですが、for を3重で回しており、処理速度が遅過ぎました。

public class Main {
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    List<Integer> list = new ArrayList<>();
    for (int i = 1; i <= N; i++) {
      list.add(sc.nextInt());
    }
    
    int count = 0;
    for (int i = 0; i < N; i++) {
      int target = list.get(i);
      for (int j = i + 1; j < N; j++) {
        if (target < list.get(j)) {
          int nextTarget = list.get(j);
          for (int k = j + 1; k < N; k++) {
            if (list.get(k) < nextTarget) {
              count++;
            }
          }
        }
      }
    }
    System.out.println(count);
  }
}

より良い回答を得るためのポイントとして、以下のことを考慮する必要がありました。
１．i, j, k のうち j を固定し、j より左で Aj より小さいものの数を lj , 右で Aj より小さいものの数を rj とする。
２．lj ∗ rj を足していく。
３．時間計算量は O(N2) になる。
４．Long 型で数値を扱う。

数学やこういったプログラミングに慣れていないと、案外思いつかないものかもしれません。