You are given an integer array nums and an integer threshold.

Find any subarray of nums of length k such that every element in the subarray is greater than threshold / k.

Return the size of any such subarray. If there is no such subarray, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

&nbsp;
Example 1:

Input: nums = [1,3,4,3,1], threshold = 6
Output: 3
Explanation: The subarray [3,4,3] has a size of 3, and every element is greater than 6 / 3 = 2.
Note that this is the only valid subarray.


Example 2:

Input: nums = [6,5,6,5,8], threshold = 7
Output: 1
Explanation: The subarray [8] has a size of 1, and 8 &gt; 7 / 1 = 7. So 1 is returned.
Note that the subarray [6,5] has a size of 2, and every element is greater than 7 / 2 = 3.5. 
Similarly, the subarrays [6,5,6], [6,5,6,5], [6,5,6,5,8] also satisfy the given conditions.
Therefore, 2, 3, 4, or 5 may also be returned.

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i], threshold &lt;= 109


class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        nums = [0] + nums + [0]
        stack = [0]
        for i in range(1,len(nums)):
            while nums[i] < nums[stack[-1]]:
                tmp = nums[stack.pop()]
                if tmp > threshold / (i - stack[-1] - 1):
                    return i - stack[-1] - 1
            stack.append(i)
        return -1
class Solution {
    public int validSubarraySize(int[] nums, int threshold) {
        int n = nums.length;
        int[] next_small = new int[n];
        int[] prev_small = new int[n];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        Arrays.fill(next_small, n);
        Arrays.fill(prev_small, -1);
        for(int i=1;i<n;i++){
            while(!stack.isEmpty() && nums[stack.peek()] >= nums[i]){
                stack.pop();
            }    
            if(stack.size()!=0){
                prev_small[i] = stack.peek();
            }
            stack.push(i);
        }
        stack = new Stack<>();
        stack.push(n-1);
        for(int i=n-2;i>=0;i--){
            while(!stack.isEmpty() && nums[stack.peek()] >= nums[i]){
                stack.pop();
            }    
            if(stack.size()!=0){
                next_small[i] = stack.peek();
            }
            stack.push(i);
        }
        for(int i=0;i<n;i++){
            int len = next_small[i] - prev_small[i] - 1;
            if(threshold/(double)len < nums[i]){
                return len;
            }
        }
        return -1;
    }
}
class Solution {
public:
    int validSubarraySize(vector<int>& nums, int threshold) {
        int n = nums.size();
        vector<long long> lr(n, n), rl(n, -1);
        
        vector<int> s;
        for(int i = 0; i < n; ++i) {
            while(!s.empty() and nums[i] < nums[s.back()]) {
                lr[s.back()] = i;
                s.pop_back();
            }
            s.push_back(i);
        }
        s.clear();
        for(int i = n - 1; ~i; --i) {
            while(!s.empty() and nums[i] < nums[s.back()]) {
                rl[s.back()] = i;
                s.pop_back();
            }
            s.push_back(i);
        }
        
        for(int i = 0; i < n; ++i) {
            long long length = lr[i] - rl[i] - 1;
            if(1LL * nums[i] * length > threshold) return length;
        }
        
        return -1;
    }
};
// please upvote if you like
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var validSubarraySize = function(nums, threshold) {
    /*
    Approach: Use monotonous increasing array
    */
    let stack=[];
    for(let i=0;i<nums.length;i++){
        let start = i;
        while(stack.length>0 && stack[stack.length-1][0]>nums[i]){
            let popped = stack.pop();
            let min = popped[0];
            let len = i-popped[1];
            if(min>threshold/len){
                return len;
            }
            start = popped[1];
        }
        stack.push([nums[i],start]);
    }
    let end = nums.length-1;
    for(let i=0;i<stack.length;i++){
        let len = end - stack[i][1] +1;
        let min = stack[i][0];
        if(min>threshold/len){
            return len;
        }
    }
    return -1;
};
Subarray With Elements Greater Than Varying Threshold