<p>You are given an integer array <code>nums</code> and an integer <code>threshold</code>.</p>

<p>Find any subarray of <code>nums</code> of length <code>k</code> such that <strong>every</strong> element in the subarray is <strong>greater</strong> than <code>threshold / k</code>.</p>

<p>Return<em> the <strong>size</strong> of <strong>any</strong> such subarray</em>. If there is no such subarray, return <code>-1</code>.</p>

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

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

<pre>
<strong>Input:</strong> nums = [1,3,4,3,1], threshold = 6
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

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

<pre>
<strong>Input:</strong> nums = [6,5,6,5,8], threshold = 7
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.</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], threshold &lt;= 10<sup>9</sup></code></li>
</ul>

# class Solution:
#     def validSubarraySize(self, nums: List[int], threshold: int) -> int:
#         nums = [0] + nums + [0]  # To make sure the first and last num can be processed properly
#         stack = [0]
#         # Push the indices of nums into the monotonic stack
#         for i in range(1, len(nums)):
#             while nums[i] < nums[stack[-1]]:
#                 # nums[idx] is the smallest element of the current subarray -> 
#                 # if nums[idx] > threshold / k, all elements in the subarray satisfy the condition
#                 idx = stack.pop()
#                 if nums[idx] > threshold / (i - stack[-1] - 1):
#                     return i - stack[-1] - 1
#             stack.append(i)
#         return -1

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        nums = [0] + nums + [0]
        stack = [0]  # Non-increaseing monotonic stack
        for i in range(len(nums)):
            while stack and nums[stack[-1]] > nums[i]:
                curr_idx = stack.pop()
                size = i - stack[-1] - 1
                if nums[curr_idx] > threshold // size:
                    return size
            stack.append(i)
        return -1


# nums = [1,3,4,3,1], threshold = 6
# stack =  [0, 1, 2]
# actual = [1, 3, 4]


'''Brute force...'''
# class Solution:
#     def validSubarraySize(self, nums: List[int], threshold: int) -> int:
#         n = len(nums)
#         for size in range(1, len(nums) + 1):
#             criteria = threshold / size
#             for i in range(n - size + 1):
#                 valid = True
#                 for j in range(i, i + size):
#                     if nums[j] <= criteria:
#                         valid = False
#                         break
#                 if valid:
#                     return size
#         return -1

# [1,3,4,3,1], threshold = 6
443