<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:
  # Same as 3015. Count the Number of Houses at a Certain Distance I
  def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
    if x > y:
      x, y = y, x

    def bothInRing(ringLen: int) -> List[int]:
      """
      Returns the contribution from the scenario where two houses are located
      in the ring.
      """
      res = [0] * n
      for k in range(1, (ringLen - 1) // 2 + 1):
        res[k - 1] += ringLen
      if ringLen % 2 == 0:
        res[ringLen // 2 - 1] += ringLen // 2
      return res

    def bothInTheSameLine(lineLen: int) -> List[int]:
      """
      Returns the contribution from the scenario where two houses are either
      located in the left line [1, x) or the right line (y, n].
      """
      res = [0] * n
      for k in range(1, lineLen + 1):
        res[k - 1] += lineLen - k
      return res

    def lineToRing(lineLen: int, ringLen: int) -> List[int]:
      """
      Returns the contribution from the scenario where one house is either
      located in the left line [1, x) or the right line (y, n] and the
      other house is located in the cycle.
      """
      res = [0] * n
      for k in range(1, lineLen + ringLen):
        # min(
        #   at most k - 1 since we need to give 1 to the line,
        #   at most ringLen / 2 since for length > ringLen / 2, it can always be
        #     calculated as ringLen - ringLen / 2
        # )
        maxInRingLen = min(k - 1, ringLen // 2)
        # max(at least 0, at lest k - lineLen)
        minInRingLen = max(0, k - lineLen)
        if minInRingLen <= maxInRingLen:
          # Each ring length contributes 2 to the count due to the split of
          # paths when entering the ring: One path traverses the upper half of
          # the ring, and the other traverses the lower half.
          # This is illustrated as follows:
          #   Path 1: ... -- x -- (upper half of the ring)
          #   Path 2: ... -- x -- (lower half of the ring)
          res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2
          if minInRingLen == 0:
            # Subtract 1 since there's no split.
            res[k - 1] -= 1
          if maxInRingLen * 2 == ringLen:
            # Subtract 1 since the following case only contribute one:
            #   ... -- x -- (upper half of the ring) -- middle point
            #   ... -- x -- (upper half of the ring) -- middle point
            res[k - 1] -= 1
      return res

    def lineToLine(leftLineLen: int, rightLineLen: int) -> List[int]:
      """
      Returns the contribution from the scenario where one house is in the left
      line [1, x) and the other house is in the right line (y, n].
      """
      res = [0] * n
      for k in range(leftLineLen + rightLineLen + 2):
        # min(
        #   at most leftLineLen,
        #   at most k - 1 - (x < y) since we need to give 1 to the right line
        #     and if x < y we need to give another 1 to "x - y".
        # )
        maxInLeft = min(leftLineLen, k - 1 - (x < y))
        # max(at least 1, at least k - rightLineLen - (x < y))
        minInLeft = max(1, k - rightLineLen - (x < y))
        if minInLeft <= maxInLeft:
          res[k - 1] += maxInLeft - minInLeft + 1
      return res

    ringLen = y - x + 1
    leftLineLen = x - 1
    rightLineLen = (n - y)

    ans = [0] * n
    ans = list(map(operator.add, ans, bothInRing(ringLen)))
    ans = list(map(operator.add, ans, bothInTheSameLine(leftLineLen)))
    ans = list(map(operator.add, ans, bothInTheSameLine(rightLineLen)))
    ans = list(map(operator.add, ans, lineToRing(leftLineLen, ringLen)))
    ans = list(map(operator.add, ans, lineToRing(rightLineLen, ringLen)))
    ans = list(map(operator.add, ans, lineToLine(leftLineLen, rightLineLen)))
    return [freq * 2 for freq in ans]
1033