Find the Count of Monotonic Pairs I
You are given an array of positive integers nums of length n.
We call a pair of non-negative integer arrays (arr1, arr2) monotonic if:
- The lengths of both arrays are
n. arr1is monotonically non-decreasing, in other words,arr1[0] <= arr1[1] <= ... <= arr1[n - 1].arr2is monotonically non-increasing, in other words,arr2[0] >= arr2[1] >= ... >= arr2[n - 1].arr1[i] + arr2[i] == nums[i]for all0 <= i <= n - 1.
Return the count of monotonic pairs.
Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
nums = [2,3,2]Output
4There are four good monotonic pairs satisfying the required conditions.
Example 2
Input
nums = [5,5,5,5]Output
126There are 126 monotonic pairs for four positions where every value in
nums is 5.Constraints
- 1 <= n == nums.length <= 2000
- 1 <= nums[i] <= 50