Subarray Product Less Than K

Given an array nums of positive integers and an integer k, determine the number of contiguous subarrays where the product of all the elements is less than k. Formally, for an array \( nums = [a_1,a_2,\dots,a_n] \), count the number of subarrays \( nums[i \dots j] \) (with \(1 \leq i \leq j \leq n\)) such that

[ \prod_{t=i}^{j} a_t < k ]

It is guaranteed that all elements in nums are positive. A sliding window technique can be used to solve this problem efficiently.

inputFormat

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated positive integers representing the elements of the array.

The third line contains an integer k.

outputFormat

Output a single integer representing the number of contiguous subarrays where the product of all elements is less than k.

4
10 5 2 6
100

8