<p>An array is considered <strong>special</strong> if every pair of its adjacent elements contains two numbers with different parity.</p>

<p>You are given an array of integer <code>nums</code> and a 2D integer matrix <code>queries</code>, where for <code>queries[i] = [from<sub>i</sub>, to<sub>i</sub>]</code> your task is to check that <span data-keyword="subarray">subarray</span> <code>nums[from<sub>i</sub>..to<sub>i</sub>]</code> is <strong>special</strong> or not.</p>

<p>Return an array of booleans <code>answer</code> such that <code>answer[i]</code> is <code>true</code> if <code>nums[from<sub>i</sub>..to<sub>i</sub>]</code> is special.<!-- notionvc: e5d6f4e2-d20a-4fbd-9c7f-22fbe52ef730 --></p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,4,1,2,6], queries = [[0,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[false]</span></p>

<p><strong>Explanation:</strong></p>

<p>The subarray is <code>[3,4,1,2,6]</code>. 2 and 6 are both even.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [4,3,1,6], queries = [[0,2],[2,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[false,true]</span></p>

<p><strong>Explanation:</strong></p>

<ol>
	<li>The subarray is <code>[4,3,1]</code>. 3 and 1 are both odd. So the answer to this query is <code>false</code>.</li>
	<li>The subarray is <code>[1,6]</code>. There is only one pair: <code>(1,6)</code> and it contains numbers with different parity. So the answer to this query is <code>true</code>.</li>
</ol>
</div>

<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] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;= nums.length - 1</code></li>
</ul>

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        res=[]
        even=[]
        for i in range(len(nums)):
            if nums[i]%2==0:
                even.append(True)
            else:
                even.append(False)
        pre_index=0
        for i in range(1,len(even)):
            if even[i] != even[i-1]:
                continue
            else:
                res.append((pre_index,i-1))
                pre_index=i
        res.append((pre_index,len(even)-1))
        ans=[]
        l=len(res)
        ans = []
        def binary_search_res(res, from_index):
            """Performs binary search on res to find the appropriate range."""
            low, high = 0, len(res) - 1
            while low <= high:
                mid = (low + high) // 2
                # Check if the current mid range contains `from_index`
                if res[mid][0] <= from_index <= res[mid][1]:
                    return mid
                # If `from_index` is less than the start of mid range, search left
                elif from_index < res[mid][0]:
                    high = mid - 1
                # If `from_index` is greater than the end of mid range, search right
                else:
                    low = mid + 1
            return -1  # Not found

        # Process each query
        ans = []
        for q in queries:  # O(l * log n)
            from_index = q[0]
            to_index = q[1]

            # Use binary search to find the correct range in res
            idx = binary_search_res(res, from_index)

            # If we find a valid index and the `to_index` also falls in the same range
            if idx != -1 and res[idx][0] <= from_index and res[idx][1] >= to_index:
                ans.append(True)
            else:
                ans.append(False)
        
        return ans
56000