Question
Number of Subarrays With Sum Less Than k
You are given an array of KaTeX can only parse string typed expression positive integers. Your task is to count the number of subarrays whose sum is strictly less than KaTeX can only parse string typed expression.
A subarray is a contiguous part of the array.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the size of the array and the target value.
The second line contains KaTeX can only parse string typed expression positive integers representing the array — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression positive integers representing the array — KaTeX can only parse string typed expression.
Output
Print a single integer — the total number of subarrays whose sum is strictly less than KaTeX can only parse string typed expression.
Example
Input
5 8
1 2 3 4 2
Output
9
Explanation
Valid subarrays with sum < 8:
(0,0) → 1
(0,1) → 1 + 2 = 3
(0,2) → 1 + 2 + 3 = 6
(1,1) → 2
(1,2) → 2 + 3 = 5
(2,2) → 3
(2,3) → 3 + 4 = 7
(3,3) → 4
(4,4) → 2
Total = 9 subarrays.
5 8
1 2 3 4 2
Output
9
Explanation
Valid subarrays with sum < 8:
(0,0) → 1
(0,1) → 1 + 2 = 3
(0,2) → 1 + 2 + 3 = 6
(1,1) → 2
(1,2) → 2 + 3 = 5
(2,2) → 3
(2,3) → 3 + 4 = 7
(3,3) → 4
(4,4) → 2
Total = 9 subarrays.