For problem C, there is another O(n) solution which is similar to the one with O(nlogn). Let f[i] be the number of times the element i appears in the array a. At each test case, we make p[1], p[2], ..., p[n], q[1], q[2], ..., q[n] equal to -1. Now let's have a stack st of pairs of int, bool.
If st.top().second = 0, then p[st.top().first] has a value, otherwise (st.top().second = 1) q[st.top().first] has a value.
Now, if we iterate from n down to 1, we have the following cases:
If f[i] > 2 there is no solution. If f[i] = 2, let x and y be the positions such that a[x] = a[y] = i. We can easily precalculate these positions. If p[x] = q[x] = p[y] = q[y] = -1. Then let's set p[x] and q[y] to i. Now, we'll push in our stack the values {x, 0} and {y, 1}. Beacuse p[x] != -1, while q[x] == -1, same for y. If any of p[x], q[x], p[y], q[y] is -1. Again, we don't have a solution, beacuse we can't pus these elements such that they appear on positions x and y in the array a.
If f[i] == 1 Let x be the position such that a[x] = i. Now both p[x] and q[x] have to be -1, otherwise there is no solution (just like in the last case). We can simply set p[x] and q[x] to i.
If f[i] == 0
i should be in a position such that it's not maximum. Let st.top().first be this position. If (st.top().second == 0) then we make q[st.top().first] equal to i, otherwise we make p[st.top().first] equal to i. We do these twice beacuse i appears in two arrays (p and q). If st.size() is less than 2, then we have no solution, beacuse we can't distribute the values such that they do not appear in a.
But why is it that when we take the top 2 elements of the stack we have both permutations p and q (If they are in the same permutation, the solution is wrong). Well, how about we look at the case when we push elements in the stack. That's the case with f[i] = 2. We see that we'll put the first element in p, and the other one in q. Thus, when we'll get to the case when f[i] == 0, we'll first take the pair that we have pushed when we put the other element in q, then we'll get the element we put in p.
My solution: https://codeforces.me/contest/1768/submission/188147915
*forgive me for my poor english
