678. Count Subarrays With Score Less Than K

The score of an array is the sum of its elements multiplied by its length. Given a positive array nums and an integer k, return the number of non-empty contiguous subarrays whose score is strictly less than k. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Integer — the count of qualifying subarrays.

Examples

Input: {"nums":[2,1,4,3,5],"k":10}
Output: 6
Explanation: Six subarrays have score below 10.

Input: {"nums":[1,1,1],"k":5}
Output: 5
Explanation: Five qualifying subarrays.

Input: {"nums":[3],"k":2}
Output: 0
Explanation: Score 3 is not below 2.

Constraints

• 1<=n<=10^5
• 1<=k<=10^15

Asked by