"""
Given a 0-indexed integer array nums of size n containing all numbers from 1 to n, return the number of increasing quadruplets.
A quadruplet (i, j, k, l) is increasing if:

0 <= i < j < k < l < n, and
nums[i] < nums[k] < nums[j] < nums[l].

Example 1:
Input: nums = [1,3,2,4,5]
Output: 2
Explanation:
- When i = 0, j = 1, k = 2, and l = 3, nums[i] < nums[k] < nums[j] < nums[l].
- When i = 0, j = 1, k = 2, and l = 4, nums[i] < nums[k] < nums[j] < nums[l].
There are no other quadruplets, so we return 2.

Example 2:
Input: nums = [1,2,3,4]
Output: 0
Explanation: There exists only one quadruplet with i = 0, j = 1, k = 2, l = 3, but since nums[j] < nums[k], we return 0.


Constraints:
4 <= nums.length <= 4000
1 <= nums[i] <= nums.length
All the integers of nums are unique. nums is a permutation.

hints:
1 Can you loop over all possible (j, k) and find the answer?
2 We can pre-compute all possible (i, j) and (k, l) and store them in 2 matrices.
3 The answer will the sum of prefix[j][k] * suffix[k][j].

analysis:
dp[j] stores the count of all valid triplets (i, j, k) that satisfies i < j < k and nums[i] < nums[k] < nums[j] (132 Pattern) and using the current number in j.
TC: O(N^2)
"""
from typing import List


class CountIncreasingQuadruplets:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        res = 0
        for j in range(n):
            prev_small = 0
            for i in range(j):
                if nums[i] < nums[j]:  # 2 meets 4
                    prev_small += 1
                    res += dp[i]    # add all 132 patterns count
                elif nums[i] > nums[j]:  # 3 meets 2
                    dp[i] += prev_small   # add all 1?2 patterns count
        return res
