The algorithm presented below assumes that there exists a solution. Checking if a solution actually exists can be added pretty easily to the algorithm.

We will construct the permutation ~A_1, \dots, A_{2N-1}~ incrementally, in a greedy manner. Let ~vmin~ and ~vmax~ be two variables, initially set to ~0~ and ~2N~. Let used be a binary array with ~2N+1~ elements, which is all set to ~0~, except for ~used_0~ and ~used_{2N}~, which are set to ~1~.

The function updateVmin() proceeds as follows: as long as ~used_{vmin} = 1~, it increments ~vmin~. The function updateVmax() proceeds as follows: as long as ~used_{vmax} = 1~, it decrements ~vmax~.

The overall algorithm proceeds as follows. First, we have ~A_1 = B_1~ (and then we set ~used_{A_1} = 1~). Then:

for i=2 to N do {
    if (B[i] is equal to B[i-1]) then {
        // add to the permutation the smallest and the largest unused elements.
        updateVmin()
        A[2*i-2]=vmin; used[vmin]=1
        updateVmax()
        A[2*i-1]=vmax; used[vmax]=1
    }
    if (B[i]>B[i-1]) {
        if (used[B[i]] is equal to 0) {
            // B[i] has not been added to the permutation, yet.
            // Add B[i] to the permutation and the largest unused element.
            A[2*i-2]=B[i]; used[B[i]]=1
            updateVmax()
            A[2*i-1]=vmax; used[vmax]=1
        } else {
            // B[i] already exists in the permutation.
            // Add the largest two unused elements.
            updateVmax()
            A[2*i-2]=vmax; used[vmax]=1
            updateVmax()
            A[2*i-1]=vmax; used[vmax]=1
        }
    }
    if (B[i]<B[i-1]) {
        if (used[B[i]] is equal to 0) {
            // B[i] has not been added to the permutation, yet.
            // Add B[i] to the permutation and the smallest unused element.
            A[2*i-2]=B[i]; used[B[i]]=1
            updateVmin()
            A[2*i-1]=vmin; used[vmin]=1
        } else {
            // B[i] already exists in the permutation.
            // Add the smallest two unused elements.
            updateVmin()
            A[2*i-2]=vmin; used[vmin]=1
            updateVmin()
            A[2*i-1]=vmin; used[vmin]=1
        }
    }
}

The time complexity of the algorithm is ~\mathcal{O}(N)~.

Proof of correctness:

We first define ~lower(i) = i-1~ and ~upper(i) = 2N+1-i~. Note that, when a solution exists, we always have ~B_i > lower(i)~ and ~B_i < upper(i)~ (that means none of the numbers ~1, \dots, i-1~, or ~2N+1-i, \dots, 2N-1~ can be the ~i^\text{th}~ median or any median after the ~i^\text{th}~). We will prove that whenever we add ~vmin~ to the permutation, we have ~vmin \le lower(i)~ and whenever we add ~vmax~ to the permutation, we have ~vmax \ge upper(i)~. If that is the case, then it is obvious that our algorithm finds a correct solution. That's because adding ~vmin~ or ~vmax~ to the permutation will not interfere in any way with the values of the medians after the current index ~i~.

A solution does not exist when ~B_i~ does not obey the inequalities regarding ~lower(i)~ and ~upper(i)~ or when ~B_i~ and ~B_{i-1}~ are not adjacent in the sorted order of all the first ~2i-1~ elements of the permutation. Note that, if our claim regarding ~vmin~ and ~vmax~ is true, then our algorithm cannot cause any of the previous conditions to occur (unless the ~B_i~ values do not allow for any solution).

We will consider several cases (for ~2 \le i \le N~). We will always assume that we have ~lower(i) < B_i < upper(i)~ (otherwise, we know from the start that there is no solution).

Case 1: ~B_i = B_{i-1}~

We need to add ~vmin~ and ~vmax~ to the permutation.

Let's assume that all the numbers ~1, \dots, lower(i)~ are already in the permutation before considering the ~i^\text{th}~ median (and thus, we will have ~vmin > lower(i)~). In this case, the median ~B_{i-1}~ of the first ~2(i-1)-1~ elements of the permutation must be exactly ~i-1~ (because there would be exactly ~i-2~ elements smaller than it in the permutation). However, ~B_i~ cannot be equal to ~i-1~, because ~i-1 = lower(i)~. Thus, we cannot have ~B_i = B_{i-1}~. This contradicts our initial assumptions, leading us to the conclusion that at least one of the numbers ~1, \dots, lower(i)~ was not used among the first ~2(i-1)-1~ elements of the permutation. ~vmin~ will be equal to one of the numbers not used which are at most equal to ~lower(i)~ and, thus, we will have ~vmin \le lower(i)~.

The proof is similar for ~vmax~ (actually, it is symmetrical).

Case 2: ~B_i < B_{i-1}~

Subcase 2.1: ~B_i~ does not appear as a median before the index ~i~.

We assume our claim to be correct for the first ~i-1~ medians and we will prove it to be correct for the first ~i~ medians. This means that neither ~vmin~ or ~vmax~ were ever equal to ~B_i~. Thus, ~B_i~ does not exist in the permutation so far and we can add it. As for ~vmin~ (which must also be added to the permutation), we will show that ~vmin \le lower(i)~.

As before, let's assume that all the numbers ~1, \dots, lower(i)~ occur among the first ~2(i-1)-1~ elements of the permutation. But then we must have ~B_{i-1} = i-1~. And, since ~B[i] > lower(i)~, we would have ~B_i > B_{i-1}~ (but this contradicts our initial assumption!).

Subcase 2.2: ~B_i~ appeared as a median at some previous index (possibly more than once).

As in the previous subcase, we assume that our claim is correct for the first ~i-1~ medians and then we will prove that it is also correct for the first ~i~ medians.

We will need to add ~vmin~ to the permutation two times. Thus, we have to prove that at least two elements among the set ~1, \dots, lower(i)~ have not been used, yet. Let's assume first that all the elements ~1, \dots, lower(i)~ were used among the first ~2(i-1)-1~ elements of the permutation. This case is handled as in the previous subcase (the obtained contradiction is, again, that ~B_i > B_{i-1}~).

Let's assume now that all the elements ~1, \dots, lower(i)~ have been used among the first ~2(i-1)-1~ elements of the permutation, except one (whose value we denote by ~X~). In this case, we have ~B_{i-1} > lower(i) = i-1~. Since ~B_i~ appeared before as a median, it must a value adjacent to ~B_{i-1}~ (in the sorted order of all the first ~2(i-1)-1~ elements of the permutation). Note how the value just before ~B_{i-1}~ in the sorted order is exactly ~lower(i) = i-1~ (because ~lower(i)~ is the ~(i-2)^\text{nd}~ elements in the sorted order). Thus, we obtain ~B[i] = lower(i)~. But this contradicts our general assumption that ~B[i] > lower(i)~.

Case 3: ~B_i > B_{i-1}~.

This case is handled similarly to Case 2, but in a symmetrical manner (it also has two subcases).