Maintain an integer set, which allows more than one identical integer in the set.
The integer set supports the following operations:
- `I x` : Insert. Insert x into the set. Note that you still have to insert the integer even if there exists at least one x in the set. Print the size of the set(number of distinct integers) after finishing the operation.
- `D x` : Delete. If x is in the set, remove one of x from the integer set. If x is not in the set, don't do anything. Print the size of the set(number of distinct integers) after finishing the operation.
- `C x` : Count. Print the occurrence of x in the integer set. If x is not in the set, print "0".
- `L x` : Lower bound. Print the smallest element greater than or equal to x in the set. If the element doesn't exist, print "-1".
- `U x` : Upper bound. Print the smallest element greater than x in the set. If the element doesn't exist, print "-1".
There are at least two ways to get AC.
One is to write a binary search tree by yourself. The template below gives the functions of the BST for reference.
Another way is to use std::map<int, int> and maintain the set by functions in the standard library.
Note: The numbers x in this problem are generated randomly.
The first line is an integer $n$ which is the number of operations.
Following n lines, each line contains one of the operations described above.
Restrictions
- 1 <= n <= 105
- 1 <= x <= 109 for every x in all operations
For each operation:
- `I x` or `D x` : Print the number of distinct integers in the set after finishing the operation.
- `C x` : Print the occurrence of x in the set. If x is not in the set, print "0".
- `L x` or `U x` : Print the element if the required element is in the set. Otherwise, print "-1".