<p>You are given an integer <code>n</code> representing an array <code>colors</code> of length <code>n</code> where all elements are set to 0&#39;s meaning <strong>uncolored</strong>. You are also given a 2D integer array <code>queries</code> where <code>queries[i] = [index<sub>i</sub>, color<sub>i</sub>]</code>. For the <code>i<sup>th</sup></code> <strong>query</strong>:</p>

<ul>
	<li>Set <code>colors[index<sub>i</sub>]</code> to <code>color<sub>i</sub></code>.</li>
	<li>Count adjacent pairs in <code>colors</code> set to the same color (regardless of <code>color<sub>i</sub></code>).</li>
</ul>

<p>Return an array <code>answer</code> of the same length as <code>queries</code> where <code>answer[i]</code> is the answer to the <code>i<sup>th</sup></code> query.</p>

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

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

<p><strong>Output:</strong> <span class="example-io">[0,1,1,0,2]</span></p>

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

<ul>
	<li>Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.</li>
	<li>After the 1<sup>st</sup> query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.</li>
	<li>After the 2<sup>nd</sup> query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.</li>
	<li>After the 3<sup>rd</sup> query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.</li>
	<li>After the 4<sup>th</sup> query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.</li>
	<li>After the 5<sup>th</sup> query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.</li>
</ul>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1, queries = [[0,100000]]</span></p>

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

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

<p>After the 1<sup>st</sup> query colors = [100000]. The count of adjacent pairs with the same color is 0.</p>
</div>

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

<ul>
	<li><code>1 &lt;= n &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&nbsp;== 2</code></li>
	<li><code>0 &lt;= index<sub>i</sub>&nbsp;&lt;= n - 1</code></li>
	<li><code>1 &lt;=&nbsp; color<sub>i</sub>&nbsp;&lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        arr = [0]*n
        ranges_start = {}
        ranges_end = {}

        result = [0]
        arr[queries[0][0]] = queries[0][1]
        ranges_start[queries[0][0]] = (queries[0][0], queries[0][0])
        ranges_end[queries[0][0]] = (queries[0][0], queries[0][0])

        for i, color in queries[1:]:
            res = result[-1]
            if i!=0 and i!=n-1 and arr[i-1] == arr[i] and arr[i] == arr[i+1] and color != arr[i] and arr[i+1] != 0:
                rang = ()
                for start, end in ranges_start.values():
                    if i > start and i < end:
                        rang = (start, end)
                        break
                
                del ranges_end[rang[1]]
                del ranges_start[rang[0]]

                new_range = (rang[0], i-1)
                ranges_start[new_range[0]] = new_range
                ranges_end[new_range[1]] = new_range

                new_range = (i+1, rang[1])

                ranges_start[new_range[0]] = new_range
                ranges_end[new_range[1]] = new_range
                res-=2

            elif i!=0 and arr[i-1] == arr[i] and color != arr[i] and arr[i-1] != 0:
                range_left = ranges_end[i]
                del ranges_end[i]
                new_range = (range_left[0], i-1)

                ranges_start[new_range[0]] = new_range
                ranges_end[new_range[1]] = new_range
                res-=1

            elif i!=n-1 and arr[i+1] == arr[i] and color != arr[i] and arr[i+1] != 0:
                range_right = ranges_start[i]
                del ranges_start[i]
                new_range = (i+1, range_right[1])

                ranges_start[new_range[0]] = new_range
                ranges_end[new_range[1]] = new_range
                res-=1

            if color != arr[i]:

                arr[i] = color

                if i!=0 and i!=n-1 and arr[i-1] == arr[i] and arr[i] == arr[i+1]:
                    range_left = ranges_end[i-1]
                    range_right = ranges_start[i+1]

                    del ranges_end[i-1]
                    del ranges_start[i+1]

                    new_range = (range_left[0], range_right[1])
                    res+=2
                
                elif i!=0 and arr[i-1] == arr[i]:
                    range_left = ranges_end[i-1]
                    del ranges_end[i-1]
                    new_range = (range_left[0], i)
                    res+=1

                elif i!=n-1 and arr[i+1] == arr[i]:
                    range_right = ranges_start[i+1]
                    del ranges_start[i+1]
                    new_range = (i, range_right[1])
                    res+=1
            
                else:
                    new_range = (i, i)

                ranges_start[new_range[0]] = new_range
                ranges_end[new_range[1]] = new_range

            result.append(res)

        return result
            

56600