The intended solution is to build the array from left to right.

The problem is now, given a known prefix of the array, can you determine the next element?

We will represent a query on the interval ~[L, R]~ as ~Q(L, R)~.

Lets assume the first ~X~ elements of the array have already been determined, i.e ~B_1, B_2, ... B_X~ have been determined. To determine ~B_{X+1}~ we can first do a query on the interval ~[1, X+1]~. There are now two cases.

Case 1: ~Q(1, X+1) = Q(1, X) + 1~

If ~Q(1, X+1) = Q(1, X) + 1~, it's clear that ~B_{X+1}~ will not have appeared yet, thus we know it is a new distinct element.

Case 2: ~Q(1, X+1) = Q(1, X)~

This implies that ~B_{X+1}~ has already appeared among the first ~X~ elements, we just have to determine which one it is.

The key observation is that ~1 = Q(X+1, X+1) \leq Q(X, X+1) \leq Q(X - 1, X+1) \leq Q(X - 2, X+1) \space ... \leq Q(1, X+1)~, i.e ~Q(i, X+1)~ is monotonically increasing as ~i~ decreases. Clearly this is true since the number of distinct elements can only increase as the left end decreases. This motivates a binary search solution. Let ~C~ be a sorted array consisting of the indices of the last occurence of every distinct element in ~B_1, B_2, ... B_X~. Observe that if ~B_{X+1} = B_{C[i]}~ then ~Q(C[i], X) = Q(C[i], X + 1)~. In fact for all ~j < i~ we will have ~Q(C[j], X) = Q(C[j], X+1)~ (why?). With this in mind we can simply determine the last index of ~C~ where the equality holds with binary search, this index will be equal to ~B_{X+1}~. After determining ~B_{X+1}~, update the array ~C~ so that it considers ~B_{X+1}~ as a last occurence of some element.

The query complexity of this algorithm is ~(N-K) \log K~, where ~K~ is the number of distinct elements in the array. With proper implementation, this should fit within the ~50000~ query limit. Partial points are meant for sub-optimal implementations of the full solution.

Time Complexity: ~\mathcal{O}(N^2)~