Count Increasing Quadruplets

Count the number of index quadruplets (i<j<k<l) in a permutation nums of 1..n such that nums[i] < nums[k] < nums[j] < nums[l]. With n up to 4000 the challenge is to avoid the O(n^4) brute force and use combinatorial counting or indexed data structures (prefix/suffix counts, BIT) to count these patterns efficiently.