<p>Given an integer array <code>nums</code> containing <code>n</code> integers, find the <strong>beauty</strong> of each subarray of size <code>k</code>.</p>

<p>The <strong>beauty</strong> of a subarray is the <code>x<sup>th</sup></code><strong> smallest integer </strong>in the subarray if it is <strong>negative</strong>, or <code>0</code> if there are fewer than <code>x</code> negative integers.</p>

<p>Return <em>an integer array containing </em><code>n - k + 1</code> <em>integers, which denote the </em><strong>beauty</strong><em> of the subarrays <strong>in order</strong> from the first index in the array.</em></p>

<ul>
	<li>
	<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>
	</li>
</ul>

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

<pre>
<strong>Input:</strong> nums = [1,-1,-3,-2,3], k = 3, x = 2
<strong>Output:</strong> [-1,-2,-2]
<strong>Explanation:</strong> There are 3 subarrays with size k = 3. 
The first subarray is <code>[1, -1, -3]</code> and the 2<sup>nd</sup> smallest negative integer is -1.&nbsp;
The second subarray is <code>[-1, -3, -2]</code> and the 2<sup>nd</sup> smallest negative integer is -2.&nbsp;
The third subarray is <code>[-3, -2, 3]&nbsp;</code>and the 2<sup>nd</sup> smallest negative integer is -2.</pre>

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

<pre>
<strong>Input:</strong> nums = [-1,-2,-3,-4,-5], k = 2, x = 2
<strong>Output:</strong> [-1,-2,-3,-4]
<strong>Explanation:</strong> There are 4 subarrays with size k = 2.
For <code>[-1, -2]</code>, the 2<sup>nd</sup> smallest negative integer is -1.
For <code>[-2, -3]</code>, the 2<sup>nd</sup> smallest negative integer is -2.
For <code>[-3, -4]</code>, the 2<sup>nd</sup> smallest negative integer is -3.
For <code>[-4, -5]</code>, the 2<sup>nd</sup> smallest negative integer is -4.&nbsp;</pre>

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

<pre>
<strong>Input:</strong> nums = [-3,1,2,-3,0,-3], k = 2, x = 1
<strong>Output:</strong> [-3,0,-3,-3,-3]
<strong>Explanation:</strong> There are 5 subarrays with size k = 2<strong>.</strong>
For <code>[-3, 1]</code>, the 1<sup>st</sup> smallest negative integer is -3.
For <code>[1, 2]</code>, there is no negative integer so the beauty is 0.
For <code>[2, -3]</code>, the 1<sup>st</sup> smallest negative integer is -3.
For <code>[-3, 0]</code>, the 1<sup>st</sup> smallest negative integer is -3.
For <code>[0, -3]</code>, the 1<sup>st</sup> smallest negative integer is -3.</pre>

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

<ul>
	<li><code>n == nums.length&nbsp;</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
	<li><code>1 &lt;= x &lt;= k&nbsp;</code></li>
	<li><code>-50&nbsp;&lt;= nums[i] &lt;= 50&nbsp;</code></li>
</ul>

from sortedcontainers import SortedList

class Solution:
  def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
    class Observer(SlidingWindow.Observer):
      
      def start_run(self, _range):
        self.list = SortedList()

      def enter_cell(self, ri):
        self.list.add(self.seq[ri])

      def exit_cell(self, li):
        self.list.remove(self.seq[li])

    result = []
    obs = Observer()
    for li, ri in LengthBoundSlidingWindow(nums, k, k, obs).run():
      num = obs.list[x - 1]
      result.append(num if num < 0 else 0)
    return result
        

from collections.abc import Sequence


class SlidingWindow:
  """Represents a sliding window algorithm framework.

  This class provides a structure for implementing sliding window algorithms.
  Concrete implementations should inherit from this class and override the
  should_contract_left() and is_window_good() methods.
  """

  class Observer:

    def init(self, sequence: Sequence):
      self.seq = sequence

    def start_run(self, _range):
      ...

    def finish_run(self):
      ...

    def enter_cell(self, right_idx: int):
      ...

    def exit_cell(self, left_idx: int):
      ...

  def __init__(self, sequence: Sequence, observer=None):
    self.seq = sequence
    self.observer = observer if observer is not None else self.Observer()
    self.observer.init(sequence)

  def should_contract_left(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def is_window_good(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def run(self, _range=None):
    _range = _range if _range is not None else range(len(self.seq))
    self.observer.start_run(_range)
    li = _range.start
    for ri in _range:
      self.observer.enter_cell(ri)
      while li <= ri and self.should_contract_left(li, ri):
        self.observer.exit_cell(li)
        li += _range.step
      if li <= ri and self.is_window_good(li, ri):
        yield li, ri
    self.observer.finish_run()


class LengthBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_len: int, max_len: int, observer=None):
    super().__init__(sequence, observer)
    self.min_len = min_len
    self.max_len = max_len

  def should_contract_left(self, li: int, ri: int) -> bool:
    return ri - li + 1 > self.max_len

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_len <= ri - li + 1 <= self.max_len


class AggregateBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_value, max_value, observer=None):
    super().__init__(sequence, observer)
    self.min_value = min_value
    self.max_value = max_value

  def should_contract_left(self, li: int, ri: int) -> bool:
    return self.observer.aggregate() > self.max_value

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_value <= self.observer.aggregate() <= self.max_value


class Sum(SlidingWindow.Observer):

  def start_run(self, _range):
    self.sum = 0

  def enter_cell(self, ri: int):
    self.sum += self.seq[ri]

  def exit_cell(self, li: int):
    self.sum -= self.seq[li]

  def aggregate(self):
    return self.sum


class Min(SlidingWindow.Observer):

  def start_run(self, _rnage):
    from collections import deque
    self._queue = deque()

  def enter_cell(self, ri: int):
    while self._queue and self.seq[self._queue[-1]] > self.seq[ri]:
      self._queue.pop()
    self._queue.append(ri)

  def exit_cell(self, li: int):
    while self._queue and self._queue[0] <= li:
      self._queue.popleft()

  def min(self):
    return self.seq[self.min_idx()]

  def min_idx(self):
    assert self._queue
    return self._queue[0]

4137