<p>You are given an integer array <code>nums</code> and two integers <code>minK</code> and <code>maxK</code>.</p>

<p>A <strong>fixed-bound subarray</strong> of <code>nums</code> is a subarray that satisfies the following conditions:</p>

<ul>
	<li>The <strong>minimum</strong> value in the subarray is equal to <code>minK</code>.</li>
	<li>The <strong>maximum</strong> value in the subarray is equal to <code>maxK</code>.</li>
</ul>

<p>Return <em>the <strong>number</strong> of fixed-bound subarrays</em>.</p>

<p>A <strong>subarray</strong> is a <strong>contiguous</strong> part of an array.</p>

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

<pre>
<strong>Input:</strong> nums = [1,3,5,2,7,5], minK = 1, maxK = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> The fixed-bound subarrays are [1,3,5] and [1,3,5,2].
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,1,1,1], minK = 1, maxK = 1
<strong>Output:</strong> 10
<strong>Explanation:</strong> Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], minK, maxK &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution {
    // count subarrays in this array, knowing that all elements are between min and max
    static long long countSubarraysFiltered(vector<int>::const_iterator start, vector<int>::const_iterator end, int minK, int maxK) {
        // result is just the number of subarrays that contain both minK and maxK
        long long result = 0;
        while (start != end) {
            auto firstMin = find(start, end, minK);
            auto firstMax = find(start, end, maxK);
            auto subrangeStart = min(firstMin, firstMax);
            auto subrangeEnd = max(firstMin, firstMax);
            if (subrangeEnd == end) {
                break;
            }
            result += (subrangeStart - start + 1) * (end - subrangeEnd);
            start = subrangeStart + 1;
        }
        return result;
    }
public:
    static long long countSubarrays(const vector<int>& nums, int minK, int maxK) {
        vector<int>::const_iterator left = nums.begin();
        long long result = 0;
        while (left != nums.end()) {
            // find first valid
            while (left != nums.end() && (*left < minK || *left > maxK)) {
                ++left;
            }
            if (left == nums.end()) {
                break;
            }
            // find valid end
            vector<int>::const_iterator right = left + 1;
            while (right != nums.end() && *right >= minK && *right <= maxK) {
                ++right;
            }
            result += countSubarraysFiltered(left, right, minK, maxK);
            left = right;
        }
        return result;
    }
};
84000