<p>You are given three <strong>positive</strong> integers <code>n</code>, <code>x</code>, and <code>y</code>.</p>

<p>In a city, there exist houses numbered <code>1</code> to <code>n</code> connected by <code>n</code> streets. There is a street connecting the house numbered <code>i</code> with the house numbered <code>i + 1</code> for all <code>1 &lt;= i &lt;= n - 1</code> . An additional street connects the house numbered <code>x</code> with the house numbered <code>y</code>.</p>

<p>For each <code>k</code>, such that <code>1 &lt;= k &lt;= n</code>, you need to find the number of <strong>pairs of houses</strong> <code>(house<sub>1</sub>, house<sub>2</sub>)</code> such that the <strong>minimum</strong> number of streets that need to be traveled to reach <code>house<sub>2</sub></code> from <code>house<sub>1</sub></code> is <code>k</code>.</p>

<p>Return <em>a <strong>1-indexed</strong> array </em><code>result</code><em> of length </em><code>n</code><em> where </em><code>result[k]</code><em> represents the <strong>total</strong> number of pairs of houses such that the <strong>minimum</strong> streets required to reach one house from the other is </em><code>k</code>.</p>

<p><strong>Note</strong> that <code>x</code> and <code>y</code> can be <strong>equal</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/20/example2.png" style="width: 474px; height: 197px;" />
<pre>
<strong>Input:</strong> n = 3, x = 1, y = 3
<strong>Output:</strong> [6,0,0]
<strong>Explanation:</strong> Let&#39;s look at each pair of houses:
- For the pair (1, 2), we can go from house 1 to house 2 directly.
- For the pair (2, 1), we can go from house 2 to house 1 directly.
- For the pair (1, 3), we can go from house 1 to house 3 directly.
- For the pair (3, 1), we can go from house 3 to house 1 directly.
- For the pair (2, 3), we can go from house 2 to house 3 directly.
- For the pair (3, 2), we can go from house 3 to house 2 directly.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/20/example3.png" style="width: 668px; height: 174px;" />
<pre>
<strong>Input:</strong> n = 5, x = 2, y = 4
<strong>Output:</strong> [10,8,2,0,0]
<strong>Explanation:</strong> For each distance k the pairs are:
- For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4).
- For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3).
- For k == 3, the pairs are (1, 5), and (5, 1).
- For k == 4 and k == 5, there are no pairs.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/20/example5.png" style="width: 544px; height: 130px;" />
<pre>
<strong>Input:</strong> n = 4, x = 1, y = 1
<strong>Output:</strong> [6,4,2,0]
<strong>Explanation:</strong> For each distance k the pairs are:
- For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
- For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
- For k == 3, the pairs are (1, 4), and (4, 1).
- For k == 4, there are no pairs.
</pre>

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

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= x, y &lt;= n</code></li>
</ul>

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        intervals = []
        # [(distance to current node, how many steps to make)]
        # e.g. if we are DIST edges from start and want to jump JUMPS times
        # then interval would look like (DIST, JUMPS)
        def add_interval(cur, edge_cnt):
            if edge_cnt == 0: return
            intervals.append((cur, edge_cnt))
            # if we had to calculate the sum of all distances
            # this function would be equal to
            # ans += (cur+1 + cur+edge_cnt) * edge_cnt // 2

        if x > y:
            x, y = y, x
        
        # * - * - * - X - * - * - Y - * - * - *
        #     ^zone1      ^zone2      ^zone3
        zone1 = x-1
        zone2 = y-x
        zone3 = n-y
    
        def handle_zone1_start(i):
            add_interval(0, i-1)
            add_interval(0, x-i)
            cur = x-i
            # reached x

            if x != y:
                edges_left = zone2-2
                add_interval(cur, (edges_left//2) + 1)
                add_interval(cur, (edges_left//2) + 1)
                if edges_left & 1:
                    add_interval(cur+1+edges_left//2, 1)
                cur += 1
            # reached y
            
            add_interval(cur, zone3)
            
        def handle_zone2_start(i):
            tox = i-x  # distance to x
            toy = y-i  # distance to y
            nearest = min(tox, toy)
            edges_left = max(tox, toy) - nearest
            add_interval(0, nearest + (edges_left//2))
            add_interval(0, nearest + (edges_left//2))
            if edges_left & 1:
                add_interval(nearest + (edges_left//2), 1)

            tox = min(tox, toy+1)
            toy = min(toy, tox+1)
            # reached x, y
            
            add_interval(tox, zone1)
            add_interval(toy, zone3)
    
        def handle_zone3_start(i):
            add_interval(0, n-i)
            add_interval(0, i-y)
            cur = i-y
            # reached y

            if x != y:
                edges_left = zone2-2
                add_interval(cur, (edges_left//2) + 1)
                add_interval(cur, (edges_left//2) + 1)
                if edges_left & 1:
                    add_interval(cur+1+edges_left//2, 1)
                cur += 1
            # reached x
            
            add_interval(cur, zone1)


        for i in range(1, n+1):
            if i <= x:
                handle_zone1_start(i)
            elif x < i < y:
                handle_zone2_start(i)
            else:
                handle_zone3_start(i)

        ans = [0]*n
        intervals.sort(key=lambda i: (i[0],-i[1]))
        h = []
        step = 0
        def make_step():
            nonlocal step, ans, h
            step += 1
            ans[step-1] += len(h)
            while h and h[0] <= step:
                heapq.heappop(h) 

        for i in range(len(intervals)-1):
            cur, edge_cnt = intervals[i]
            heapq.heappush(h, step+edge_cnt)
            next_step = intervals[i+1][0]
            while step < next_step:
                make_step()
        cur, edge_cnt = intervals[-1]
        heapq.heappush(h, step+edge_cnt)
        while h:
            make_step()

        return ans
4650