We will describe a "divide and conquer" algorithm that, given an array ~A~ of length ~N~, finds the shortest subsequence that contains all numbers from ~1~ to ~K~.

solve(T):
    L = left half of array T
    R = right half of array T
    X = solve(L)
    Y = solve(R)
    Z = the shortest subsequence that contains all numbers from 1 to K,
        and is comprised of the suffix of array L and the prefix of array R
    return min(X, Y, Z)

If we can calculate the value ~Z~ in the complexity ~\mathcal O(\text{length of array }T)~, then the algorithm's complexity is ~\mathcal O(N \log N)~.

How to determine the value ~Z~? For each suffix of the array ~L~, we will calculate a bitmask that describes a set of numbers that is in that suffix (~K \le 50~ so that bitmask will be a single long long). We will do the same thing for each prefix of array ~R~. Now we want to find two bitmasks whose binary or is equal to ~2^K-1~, and the sum of the lengths of the corresponding suffix and prefix is minimal. Notice that there are at most ~K~ interesting bitmasks from the left and from the right side, so we can do this in ~\mathcal O(K^2)~ by trying out all pairs of bitmasks. We can use the "monotonous" property of the bitmasks so we can achieve the same result in ~\mathcal O(K)~.

Nevertheless, this is not quick enough because we have ~M~ queries that need to be answered.

We will construct a tournament tree where each node stores "interesting" sets of bitmasks for prefixes and suffixes of its interval and the shortest subsequence that contains all numbers from ~1~ to ~K~ in its interval. Then the merging of nodes in the tree actually corresponds to the step of the aforementioned algorithm. When we modify a number in the array, we need to recalculate the values in ~\mathcal O(\log N)~ nodes, so the complexity of a single change is ~\mathcal O(K \log N)~, and the total complexity is ~\mathcal O(KN \log N + KM \log N)~.