B"This is a hard version of this problem. The only difference between the versions is that you have to solve the hard version in online mode. You can make hacks only if both versions of the problem are solved. You have an array a , which is initially empty. You need to process queries of the following types: The first line contains an integer q ( 1 <= q q <= q 10^6 ) -- the number of queries. The next q lines contain the queries as described above. It is guaranteed that It is also guaranteed that the number of queries of the fourth type (?) does not exceed 10^5 . Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query, so don't forget to flush output after printing answers. You can use functions like fflush(stdout) in C++ and BufferedWriter.flush in Java or similar after each writing in your program. For each query of the fourth type output one integer -- the number of distinct elements in array a at the moment of query. In the first example array a changes as follows: In the second example array a changes as follows: "...