<p>You are given an integer array <code>nums</code> of length <code>n</code>, and an integer array <code>queries</code> of length <code>m</code>.</p>

<p>Return <em>an array </em><code>answer</code><em> of length </em><code>m</code><em> where </em><code>answer[i]</code><em> is the <strong>maximum</strong> size of a <strong>subsequence</strong> that you can take from </em><code>nums</code><em> such that the <strong>sum</strong> of its elements is less than or equal to </em><code>queries[i]</code>.</p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

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

<pre>
<strong>Input:</strong> nums = [4,5,2,1], queries = [3,10,21]
<strong>Output:</strong> [2,3,4]
<strong>Explanation:</strong> We answer the queries as follows:
- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,3,4,5], queries = [1]
<strong>Output:</strong> [0]
<strong>Explanation:</strong> The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.</pre>

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

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>m == queries.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i], queries[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort(key=lambda num: num)

        queries = [[idx, val] for idx, val in enumerate(queries)]

        queries.sort(key=lambda query: query[1])

        def binary_search(start, end, target, s):
            if start > end:
                return -1

            if start == end:
                is_target = nums[start] <= target and start not in s
                return start if is_target else -1

            mid = (start + end) // 2

            if mid not in s:
                pos = binary_search(start, mid - 1, target, s)

                if pos > -1:
                    return pos

                return mid if nums[mid] <= target else -1


            return binary_search(mid + 1, end, target, s)
        
        subseqs_sizes = [0 for i in range(len(queries))]
        prev_val = 0
        prev_size = 0

        s = set()

        for i in range(len(queries)):
            target = queries[i][1]
            size = 0

            if i > 0:
                target -= prev_val
                size = prev_size


            pos = binary_search(0, len(nums) - 1, target, s)

            while pos > -1:
                size += 1
                target -= nums[pos]
                s.add(pos)
                pos = binary_search(0, len(nums) - 1, target, s)

            subseqs_sizes[queries[i][0]] = size
            prev_val = queries[i][1] - target
            prev_size = size


        return subseqs_sizes


            
117