<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:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        cnttotal = [0 for _ in range(len(nums))]
        cnttouch = [0 for _ in range(len(nums))]
        lastinsofminK = [-1 for _ in range(len(nums))]
        lastinsofmaxK = [-1 for _ in range(len(nums))]
        cnttotal[0] = int(minK == maxK == nums[0])
        cnttouch[0] = int(minK == maxK == nums[0])
        lastillegal = [-1 for _ in range(len(nums))]

        if nums[0] == minK:
            lastinsofminK[0] = 0
        if nums[0] == maxK:
            lastinsofmaxK[0] = 0

        if nums[0] < minK or nums[0] > maxK:
            lastillegal[0] = 0

        for idx in range(1,len(nums)):
            newval = nums[idx]
            if newval == minK:
                lastinsofminK[idx] = idx
            else:
                lastinsofminK[idx] = lastinsofminK[idx-1]

            if newval == maxK:
                lastinsofmaxK[idx] = idx
            else:
                lastinsofmaxK[idx] = lastinsofmaxK[idx-1]

            lastillegal[idx] = lastillegal[idx-1]
            dprint("newval is ", newval)
            if newval < minK or newval > maxK:
                dprint('newval', newval, "is not legal")
                cnttotal[idx] = cnttotal[idx-1]
                cnttouch[idx] = 0
                lastillegal[idx] = idx
            elif (minK < newval < maxK) and cnttouch[idx-1] > 0:
                # Can extend all existing subarrays
                cnttouch[idx] = cnttouch[idx-1]
                cnttotal[idx] = cnttotal[idx-1] + cnttouch[idx-1] 
            elif (minK < newval < maxK) and cnttouch[idx-1] == 0:
                # Can't help, copy over
                # note: just a particular case of elif above
                cnttouch[idx] = 0
                cnttotal[idx] = cnttotal[idx-1]
            elif (minK == newval) and (maxK == newval):
                newones = max(0,idx - max(lastillegal[idx], lastinsofmaxK[idx-1]))
                cnttouch[idx] = cnttouch[idx-1] + newones
                cnttotal[idx] = cnttotal[idx-1] + cnttouch[idx]
            elif (minK == newval):
                newones = 0
                if lastinsofmaxK[idx-1] > lastinsofminK[idx-1]:
                    newones =  max(0,lastinsofmaxK[idx-1] - max(lastillegal[idx],lastinsofminK[idx-1]))
                cnttouch[idx] = cnttouch[idx-1] + newones
                cnttotal[idx] = cnttotal[idx-1] + cnttouch[idx]
            
            elif (maxK == newval):
                newones = 0
                if lastinsofmaxK[idx-1] < lastinsofminK[idx-1]:
                    newones =  max(0,lastinsofminK[idx-1] - max(lastillegal[idx],lastinsofmaxK[idx-1]))
                cnttouch[idx] = cnttouch[idx-1] + newones
                cnttotal[idx] = cnttotal[idx-1] + cnttouch[idx]

            else:
                raise Exception("implement")

        dprint("cnttotal", cnttotal)
        dprint("cnttouch", cnttouch)
        dprint("lastillegal", lastillegal)
        return cnttotal[-1]

def dprint(*args):
    if 0:
        print(*args)            
        
862