Count Increasing Quadruplets
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 < nnums[i] < nums[k] < nums[j] < nums[l]
Example 1
Input
nums = [1,3,2,4,5]Output
2For
(i, j, k, l) = (0, 1, 2, 3) and (0, 1, 2, 4), nums[i] < nums[k] < nums[j] < nums[l], and there are no other increasing quadruplets.Example 2
Input
nums = [1,2,3,4]Output
0There 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
numsare unique.numsis a permutation.