1
class Solution {
2
 public:
3
  int validSubarraySize(vector<int> &nums, int threshold) {
4
    int n = nums.size();
5
    vector<long long> lr(n, n), rl(n, -1);
6

7
    vector<int> s;
8
    for (int i = 0; i < n; ++i) {
9
      while (!s.empty() and nums[i] < nums[s.back()]) {
10
        lr[s.back()] = i;
11
        s.pop_back();
12
      }
13
      s.push_back(i);
14
    }
15
    s.clear();
16
    for (int i = n - 1; ~i; --i) {
17
      while (!s.empty() and nums[i] < nums[s.back()]) {
18
        rl[s.back()] = i;
19
        s.pop_back();
20
      }
21
      s.push_back(i);
22
    }
23

24
    for (int i = 0; i < n; ++i) {
25
      long long length = lr[i] - rl[i] - 1;
26
      if (1LL * nums[i] * length > threshold) return length;
27
    }
28

29
    return -1;
30
  }
31
};
32
// please upvote if you like