<p>The <strong>score</strong> of an array is defined as the <strong>product</strong> of its sum and its length.</p>

<ul>
	<li>For example, the score of <code>[1, 2, 3, 4, 5]</code> is <code>(1 + 2 + 3 + 4 + 5) * 5 = 75</code>.</li>
</ul>

<p>Given a positive integer array <code>nums</code> and an integer <code>k</code>, return <em>the <strong>number of non-empty subarrays</strong> of</em> <code>nums</code> <em>whose score is <strong>strictly less</strong> than</em> <code>k</code>.</p>

<p>A <strong>subarray</strong> is a contiguous sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,4,3,5], k = 10
<strong>Output:</strong> 6
<strong>Explanation:</strong>
The 6 subarrays having scores less than 10 are:
- [2] with score 2 * 1 = 2.
- [1] with score 1 * 1 = 1.
- [4] with score 4 * 1 = 4.
- [3] with score 3 * 1 = 3. 
- [5] with score 5 * 1 = 5.
- [2,1] with score (2 + 1) * 2 = 6.
Note that subarrays such as [1,4] and [4,3,5] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1], k = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong>
Every subarray except [1,1,1] has a score less than 5.
[1,1,1] has a score (1 + 1 + 1) * 3 = 9, which is greater than 5.
Thus, there are 5 subarrays having scores less than 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>15</sup></code></li>
</ul>

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        cnt, accSum = 0, 0
        left = 0
        m = 0
        for right, num in enumerate(nums):
            accSum += num
            # v = accSum * (right - m + 1)
            # n = (right - m + 1)

            while accSum*(right - left + 1) >= k:
                # n -= 1
                accSum -= nums[left]
                # v = accSum * n
                left += 1
                # m += 1

            cnt += right - left + 1
        
        return cnt

# nums = [2,1,4,3,5], k = 10
# left =0, cnt =0, prodSum = 0
# right = 0, prodSum = 2*1 = 2, cnt = 1
# right = 1, prodSum = (2 + 1) = 3, v=6, cnt += 1 - 0 + 1 = 3
# right = 2, prodSum = (2 + 1 + 4) = 7, v=21, n = 2
    # prodSum =  (1+4), v = 10 , n = 1, left = 1, m = 1
    # prodSum = (4), v = 4 < k = 10, m = 2, left=2 -> cnt += (2 - 1) + 1 = 5
# right = 3, prodSum = (4+3), v = 7*(3 - m=2 + 1) = 7*2= 1, n =3-2+1 = 2
    # n=1, prodSum = 3, v = 3*1 < 10, left = 3, m = 3, cnt += 3 - 3 + 1 = 6
# right =4, prodSUm = (3+5), v = 8*(4-m=3+1) = 8*2 = 16

823