http://codeforces.me/blog/entry/3327

Initially, we will just read the input without processing it in order to apply coordinate compression. Now for every number in the input we know its position if all numbers are sorted. For example, if we have number 9,7,1,1,8,7, the position of 1 is 1, the position of 7 is 2, the position of 8 is 3 and the position of 9 is 4.

Notice that it only matters whether number X is in the set, not how many times it is actually present. So at any moment we can keep the number of occurences for each number. When the query is '+', we increase X's count and if it becomes 1, then we need to insert X into our data structure. When the query is '-', we decrease X's count and if it becomes 0, then we need to erase X from our data structure.

Now let's see how we will build our data structure. Say that P[X] is the position of X if the array is sorted (the thing we talked about in the first paragraph) and M is the maximum value of P[X] for some X. Then we can build segment tree over those positions (indices from 1 to M). Each node in the segment tree will store the GCD of its children and initially everything is set to zero. It's easy to see that the answer after performing each query will be stored in the root of the tree. When inserting a number X into our structure, we simply assign value X to index P[X] and when erasing a number X, we assign value 0 to index P[X].

Here is my code — http://ideone.com/uJ8ndT :)

Can It be done using square root decomposition also.. Regards.