← 返回 uber 的题目列表First Unique Number
类型：online_judge
Problem: First Unique Number
Design a data structure FirstUnique that supports the following operations:
FirstUnique(nums): initialize the data structure with an integer array. The numbers are inserted into the queue in the given order.
showFirstUnique(): return the first number in the queue that appears exactly once. If no such number exists, return -1.
add(value): append value to the end of the queue.
The operations should be efficient for many queries and updates.
Input Format for Testing
The first line contains an integer n, the length of the initial array.
The second line contains n integers, the initial array nums; if n = 0, this line may be empty.
The third line contains an integer q, the number of operations.
Each of the next q lines is one operation:
show: call showFirstUnique() and print the result.
add x: call add(x) and print nothing.
Output Format
For each show operation, print one line containing the result.
Constraints
0 <= n <= 10^5
1 <= q <= 10^5
-10^9 <= nums[i], value <= 10^9
Example
Input:
3
2 3 5
7
show
add 5
show
add 2
show
add 3
show
Output:
2
2
3
-1
Example
Input
3
2 3 5
7
show
add 5
show
add 2
show
add 3
show
Output
2
2
3
-1