Simply put, the problem is asking us to represent $$$S$$$, as a summation of numbers from the set $$${1, 2, 3, … ,n }$$$.

Obviously there are many ways to do that, for example one might use $$$1$$$ $$$S$$$ times, but in this problem we are asked to use the minimum number of elements and output how many we used.

Since we have all the numbers from $$$1$$$ to $$$n$$$ and we can use each element repeatedly, we can afford to be greedy and always use the largest value less or equal to $$$S$$$, until we get the sum of the selected elements equal to $$$S$$$. This ensures that we use the fewest possible numbers.

This process can easily be represented by a ceil division of $$$S$$$ by $$$n$$$.

because $$$⌈S/n⌉$$$ tells us how many times we would need to add the largest possible number (which is $$$n$$$) to reach or exceed $$$S$$$.

Time complexity: $$$O(1)$$$. Space complexity: $$$O(1)$$$

n,S = map(int, input().split())
	
print((S + n - 1) //  n) 

We need the deque data structure to solve this problem. We iterate the given permutation starting from the first element and we append to the left of our deque either if it is empty or the element at the 0-th index of our deque is larger than the current element we are about to add to our deque. Otherwise we append to the end of our deque because appending a larger number than what we currently have at the 0-th index of our deque will definitly make our final answer lexicographically larger.

from collections import deque

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))

    ans = deque()
    for num in arr:
        if ans and num < ans[0]:
            ans.appendleft(num)
        else:
            ans.append(num)
    
    print(*ans)

Think of a queue (FIFO structure) to store the most recent k unique chats.

Use a set to quickly check if a friend's chat is already on the screen.

When a new chat arrives and the screen is full, remove the oldest chat before adding the new one.

The problem requires maintaining the most recent k unique chat messages in order.
Key observations:
1. If a friend sends multiple messages, only the first occurrence matters.
2. If the chat screen is full (k elements), the oldest message is removed when a new unique message arrives.

Approach:

• Use a deque (chat_screen) to store recent unique chats while maintaining order.
• Use a set (seen) to track which friends are currently displayed.
• Process each message:
• • If it's already in seen, ignore it.
• • Otherwise:
• • • If chat_screen is full, remove the oldest chat (last element).
• • • Add the new chat to the front of chat_screen and update seen.
• Print the final chat list.

This method ensures an O(n) time complexity, which is efficient for large inputs.

```python from collections import deque

def chat_screen(n, k, messages): chat_screen = deque() seen = set()

for id_i in messages:
    if id_i not in seen:
        if len(chat_screen) == k:
            removed = chat_screen.pop()
            seen.remove(removed)

        chat_screen.appendleft(id_i)
        seen.add(id_i)

print(len(chat_screen))
print(*chat_screen)

n, k = map(int, input().split()) messages = list(map(int, input().split())) chat_screen(n, k, messages)