Fit the Context Window

easy

A chat assistant sends the model its system prompt followed by the conversation so far. Models have a fixed context window, so when a long conversation no longer fits, the oldest messages are dropped and the most recent ones are kept. Different models have different windows, and the platform wants to know, for each of them, how much of a conversation it would see.

tokens[0] is the size of the system prompt in tokens, which is always sent. tokens[1] to tokens[n - 1] are the messages of the conversation, from oldest to newest.

For each budget budgets[j], find how many of the most recent messages can be sent together with the system prompt without the total exceeding the budget. The kept messages are always the newest ones, a contiguous run ending at the last message: an older message is never kept when a newer one was dropped. If the system prompt alone does not fit, the answer is -1.

Return the answers in the order of budgets.

Example

tokens = [50, 120, 30, 80, 40], budgets = [200, 50, 49, 1000, 170, 169].

With 200 tokens, the system prompt takes 50 and leaves 150: the newest messages take 40, then 80 (120 in total), then 30 (150), and the next one, 120, would not fit, so 3 messages are kept. With 50 the prompt fits alone (0); with 49 it does not fit (-1); with 1,000 everything fits (4). 170 leaves 120 tokens, which is 40 + 80 (2), and 169 leaves 119 (1). The answer is [3, 0, -1, 4, 2, 1].

Example 1

Input

[
  "[50,120,30,80,40]",
  "[200,50,49,1000,170,169]"
]

Output

[3,0,-1,4,2,1]

Explanation. The example.

Example 2

Input

[
  "[10]",
  "[10,9,100]"
]

Output

[0,-1,0]

Explanation. Only a system prompt.

Example 3

Input

[
  "[5,1,1,100]",
  "[50,106,107]"
]

Output

[0,2,3]

Explanation. When the newest message does not fit, nothing older is kept either.

Example 4

Input

[
  "[0,1,50,1]",
  "[3]"
]

Output

[1]

Explanation. Kept messages are the most recent run: an older short message cannot jump the queue.

Example 5

Input

[
  "[0,0,0]",
  "[0]"
]

Output

[2]

Explanation. Empty messages cost nothing.

Example 6

Input

[
  "[100,10,20,30,40,50]",
  "[99,100,149,150,190,219,220,250,1000]"
]

Output

[-1,0,0,1,2,2,3,5,5]

Explanation. Many budgets against the same conversation.

Example 7

Input

[
  "[1000000,1000000,1000000,1000000,1000000]",
  "[1000000000,2999999,3000000]"
]

Output

[4,1,2]

Explanation. Large token counts.

Follow-up: Messages now come in pairs: a user's message and the assistant's reply must be kept or dropped together. How does that change your search, and what about a single huge message in the middle that would be worth summarising rather than dropping?

Constraints:

- `1 <= tokens.length <= 10^5` - `0 <= tokens[i] <= 10^6` - `1 <= budgets.length <= 10^5` - `0 <= budgets[j] <= 10^9`

Views: 2