<p>You are given a 2D integer array <code>intervals</code>, where <code>intervals[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> describes the <code>i<sup>th</sup></code> interval starting at <code>left<sub>i</sub></code> and ending at <code>right<sub>i</sub></code> <strong>(inclusive)</strong>. The <strong>size</strong> of an interval is defined as the number of integers it contains, or more formally <code>right<sub>i</sub> - left<sub>i</sub> + 1</code>.</p>

<p>You are also given an integer array <code>queries</code>. The answer to the <code>j<sup>th</sup></code> query is the <strong>size of the smallest interval</strong> <code>i</code> such that <code>left<sub>i</sub> &lt;= queries[j] &lt;= right<sub>i</sub></code>. If no such interval exists, the answer is <code>-1</code>.</p>

<p>Return <em>an array containing the answers to the queries</em>.</p>

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

<pre>
<strong>Input:</strong> intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
<strong>Output:</strong> [3,3,1,4]
<strong>Explanation:</strong> The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
</pre>

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

<pre>
<strong>Input:</strong> intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
<strong>Output:</strong> [2,-1,4,6]
<strong>Explanation:</strong> The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
</pre>

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

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>1 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt;= 10<sup>7</sup></code></li>
	<li><code>1 &lt;= queries[j] &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals = sorted(intervals, key=lambda i:i[1]-i[0]+1)

        i = intervals[0]
        line = [(i[0]-1,-1), (i[1],i[1]-i[0]+1)]
        def search(k, l, lo, hi):
            if(hi <= lo):
                if(l[hi][0]==k):
                    return hi
                if(l[hi][0]>k):
                    return hi
                else: 
                    return hi + 1
            mid = (hi + lo)//2 + 1
            if(k >= l[mid][0]):
                return search(k, l, mid, hi)
            else:
                return search(k, l, lo, mid-1)

        for i in intervals[1:]:
            size = i[1] - i[0] + 1
            hindex = search(i[1], line, 0, len(line)-1)
            lindex = search(i[0], line, 0, len(line)-1)
            if(lindex >= len(line)): 
                if(line[lindex-1][0]<i[0]-1):
                    line.append((i[0]-1, -1))
                line.append((i[1], size))
            elif(lindex == hindex):
                if(line[hindex][1] == -1):
                    if(i[1]<line[hindex][0]):
                        line.insert(hindex, (i[1], size))
                    else:
                        line[hindex] = (line[hindex][0], size)
                if(hindex == 0 or (line[hindex-1][0]<i[0]-1)):
                    line.insert(hindex, (i[0]-1, -1))
            else:
                j = lindex
                if(line[j][1] == -1):
                    line[j] = (line[j][0], size)
                    if(j==0 or (j-1>=0 and line[j-1][0]<i[0]-1)):
                        line.insert(j, (i[0]-1, -1))
                        hindex += 1
                        j += 1

                j += 1
                while j < hindex:
                    if(line[j][1] == -1):
                        line[j] = (line[j][0], size)
                    j+= 1
                if(hindex >= len(line)):
                    line.append((i[1], size))
                elif(line[hindex][1] == -1):
                    if(i[1]<line[hindex][0]):
                        line.insert(hindex, (i[1], size))
                    else:
                        line[hindex] = (line[hindex][0], size)
            # if(lindex >= len(line)): 
            #     line.append((i[0]-1, -1))
            #     line.append((i[1], size))
            # elif(lindex == hindex):
            #     line.insert(lindex, (i[0]-1, -1))
            # elif(hindex >= len(line)): 
            #     line.append((i[1], size))
            # elif(line[hindex][1] == -1):
            #     line.insert(hindex, (i[1], size))
            #     if(lindex == hindex):
            #         line.insert(lindex, (i[0]-1, -1))
            # if(line[lindex][1] == -1 and lindex != hindex):
            #     curr, _ = line[lindex]
            #     curr = min(curr, i[0])
            #     line[lindex] = (curr, size)
            #     line.insert(lindex, (i[0]-1, -1))
        retval = []
        for q in queries:
            idx = search(q, line, 0, len(line)-1)
            if idx >= len(line):
                retval.append[-1]
            else:
                retval.append(line[idx][1])
        return retval

                
            

        # ma = max(np.max(intervals), max(queries))
        # print(f'{ma}')
        # line = [-1]*(ma+1)
        # print(len(line))
        # for i in intervals:
        #     size = i[1] - i[0] + 1
        #     for j in range(i[0], i[1]+1):
        #         if(j>=len(line)):
        #             print(j)
        #         if(line[j]==-1):
        #             line[j] = size
        #         else:
        #             line[j] = min(line[j], size)
        # retval = []
        # for q in queries:
        #     retval.append(line[q])
        # return retval
        # dq = {}
        # for i in range(len(queries)):
        #     dq[i] = queries[i]
        # dq =  dict(sorted(dq.items(), key=lambda item: item[1]))

        # intervals = sorted(intervals, key=lambda i:i[1]-i[0]+1)
        # def filter(key):  
        #     j = 0
        #     n = (len(intervals))
        #     while (j < n):
        #         i = intervals[j]
        #         if (i[0] <= key and i[1] >= key):
        #             return i[1]-i[0]+1
        #         if(i[1] < key):
        #             intervals.pop(j)
        #             n -= 1
        #         else:
        #             j += 1
        #     return -1
        # retval = [None] * len(queries)
        # for i,q in dq.items():
        #     retval[i] = (filter(q))
        
        # return retval

55662