Number of Subarrays With Product Less Than K

Given an array of positive integers and a positive integer k, count the number of contiguous subarrays such that the product of all the elements in the subarray is strictly less than k. Formally, for each contiguous subarray a[l...r], we require:

\(\prod_{i=l}^{r} a_i < k\)

This problem involves understanding and applying the sliding window technique to efficiently compute the number of subarrays that meet the above condition.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains two integers n and k separated by a space, where n is the number of elements in the array.
• The second line contains n positive integers separated by spaces representing the array.

It is guaranteed that the array contains at least one element.

outputFormat

The output is a single line printed to stdout that contains one integer: the number of contiguous subarrays whose product is strictly less than k.

4 100
10 5 2 6

8