First Unique User in a Stream

Problem: First Unique User in a Stream Design a data structure that receives user IDs in order. Each call to add(user) means a user enters the stream in chronological order: If a user appears for the first time, they are currently a first-time user. If the same user appears for the second time or more, they are no longer a first-time user. Support querying the earliest user who has appeared exactly once so far. You need to process two types of operations: add userId: add a user to the stream. first: return the earliest current first-time user; return -1 if none exists. Use a data structure that can efficiently support insertion, deletion, and querying the head element, such as a hash map plus a doubly linked list. Input Format The first line contains an integer Q, the number of operations. The next Q lines are in one of the following formats: add userId first userId is a string without spaces. Output Format For each first operation, print one line containing the answer. Constraints 1 <= Q <= 2 * 10^5 1 <= len(userId) <= 50 userId contains only non-whitespace characters such as letters, digits, and underscores. Example Input: 8 add alice add bob first add alice first add carol add bob first Output: alice bob carol Explanation: After adding alice and bob, the earliest user appearing once is alice. After alice appears again, alice is no longer a first-time user, so the answer is bob. After bob appears again, the answer becomes carol. Example Input 8 add alice add bob first add alice first add carol add bob first Output alice bob carol