## 1. Abridged problem statement

We have objects `1, 1', 2, 2', ..., n, n'`. A valid **bipermutation** is an ordering of all `2n` objects such that:

- each primed object `i'` appears before its unprimed object `i`;
- the relative order of primed objects is the same as the relative order of unprimed objects.

For `i != j`, define:

- `b_ij = j'` if `j < i`,
- `b_ij = j` if `j > i`.

For every `i`, `a(i)` is the number of `j != i` such that object `i` appears before object `b_ij`.

Given `a1, ..., an`, construct any valid bipermutation with these values, or print `NO`.

In the output, unprimed `i` is printed as `i`, and primed `i'` is printed as `-i`.

Constraints: `1 <= n <= 1000`.

---

## 2. Detailed editorial

### 2.1 Structure of a bipermutation

Because primed and unprimed objects have the same relative order, every bipermutation is determined by:

1. a permutation

```text
pi[1], pi[2], ..., pi[n]
```

which is the order of the unprimed objects;

2. positions where primed objects are inserted.

The primed objects must appear in the same order:

```text
pi[1]', pi[2]', ..., pi[n]'
```

Also, each `pi[r]'` must appear before `pi[r]`.

So a valid bipermutation is an interleaving of two equal-order copies of the same permutation, where each primed copy appears before its unprimed copy.

---

### 2.2 Contribution to `a(v)`

Suppose `v = pi[r]`.

For some `j > v`, we compare `v` with unprimed `j`.

So `j` contributes to `a(v)` iff unprimed `j` appears after `v`, i.e. `j` lies to the right of `v` in `pi`.

For some `j < v`, we compare `v` with primed `j'`.

So `j` contributes iff `j'` appears after unprimed `v`.

Therefore:

```text
a(v)
=
number of larger values already to the right of v in pi
+
number of smaller values to the right of v whose primes are also after v
```

This is the key formula.

---

### 2.3 Building the permutation from right to left

The solution constructs `pi` from right to left.

Let `picked` store already chosen values. Since we build from the end:

```text
picked[0] = pi[n]
picked[1] = pi[n - 1]
...
```

At some step `k`, we have already placed `k` values on the right.

For an unused value `v`, define:

```text
larger_picked[v] = number of already picked values greater than v
```

This is the first part of `a(v)`.

So the remaining needed contribution is:

```text
need = a[v] - larger_picked[v]
```

This must come from smaller already-picked values whose primes appear after `v`.

---

### 2.4 Representing prime positions using `g`

When placing a new value `v`, some suffix of the already picked values will have their primes after `v`.

Let:

```text
g = number of already picked values whose primes are after v
```

Because primed objects appear in the same order as unprimed objects, those `g` values are exactly:

```text
picked[0], picked[1], ..., picked[g - 1]
```

That is, the most recently picked values, i.e. the rightmost values in `pi`.

For every candidate `v`, we know positions of already picked smaller values:

```text
smaller_pos[v]
```

This vector contains indices in `picked` where values smaller than `v` occurred.

We need exactly `need` of those positions to be `< g`.

So if:

```text
smaller_pos[v] = [p0, p1, ..., p(m-1)]
```

then legal `g` must satisfy:

```text
p[need - 1] < g <= p[need]
```

with boundary cases:

- if `need = 0`, then `g` can start from `0`;
- if `need = total_smaller`, then `g` can go up to `k`.

Thus:

```text
g_lo = 0                         if need == 0
g_lo = smaller_pos[v][need-1]+1  otherwise

g_hi = k                         if need == total_smaller
g_hi = smaller_pos[v][need]      otherwise
```

Also, as we move from right to left, `g` cannot decrease. Therefore:

```text
g >= g_prev
```

So the actual minimal possible value is:

```text
cur_g = max(g_lo, g_prev)
```

Candidate `v` is legal if:

```text
cur_g <= g_hi
```

---

### 2.5 Greedy choice

At every step, among all legal unused values, choose the one with smallest possible `cur_g`.

Why?

- A smaller `g` leaves more freedom for future positions.
- Future positions require `g` to be nondecreasing, so increasing `g` too early can only hurt.
- If multiple values have the same `cur_g`, choose the smallest value. Picking a smaller value increases `larger_picked` for fewer remaining values, so it is safer.

If no legal candidate exists, the answer is `NO`.

---

### 2.6 Reconstructing the final sequence

After the greedy process:

```text
picked[0] = pi[n]
picked[1] = pi[n - 1]
...
picked[n - 1] = pi[1]
```

So:

```text
pi[r] = picked[n - r]
```

For each position `r`, the algorithm has stored `g`.

If there are `g` primes after `pi[r]`, then there are `n - g` primes before or at that point.

Define:

```text
f[r] = n - g_for_pi[r]
```

Then, before outputting unprimed `pi[r]`, output all primed objects:

```text
pi[1]', pi[2]', ..., pi[f[r]]'
```

that have not already been output.

Finally output `pi[r]`.

---

### 2.7 Complexity

There are `n` steps, and each step scans all `n` values.

Updating auxiliary arrays also costs `O(n)` per step.

Total complexity:

```text
O(n^2)
```

Memory complexity:

```text
O(n^2)
```

because `smaller_pos` may store `O(n^2)` total positions.

For `n <= 1000`, this is fine.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // The two conditions force a lot of structure: the unprimed objects appear
    // in some order pi_1, pi_2, ..., pi_n, the primed objects appear in that
    // exact same order, and every i sits before its own i'. So a bipermutation
    // is nothing more than a merge of the sequence pi with a copy of itself
    // (the primes), where the r-th prime lands somewhere after the r-th
    // unprimed.
    //
    // Against that picture b_ij just selects, for an ordered pair (i, j), which
    // copy of j to compare i against - the unprimed j when j is the larger
    // value, the primed j' when j is the smaller one. So a(i) counts the j
    // whose selected copy ends up after i, which reading off the merge is
    //
    //     a(i) = #{j > i : i before j in pi} + #{j < i : i before j' in pi}.
    //
    // The hint (i <. b_ij and j <. b_jk imply i <. b_ik) says this "i before
    // b_ij" relation is transitive, and that consistency is what lets us
    // rebuild an ordering from the a-values instead of searching blindly.
    //
    // We grow pi from the back, fixing one value at a time: step k pins down
    // pi_{n-k}, so we start by choosing the last unprimed value pi_n and end
    // with pi_1. Once v = pi_r is set, every value chosen so far sits to the
    // right of v in pi, so the first count in a(v) is just how many of them
    // exceed v, exactly larger_picked[v], while the second is how many of the
    // smaller ones have their prime land to the right of v too. The first part
    // settles as soon as we pick v; the second is still ours to set, between 0
    // and the number of smaller values placed. So v can take step k exactly
    // when larger_picked[v] <= a(v) <= k; step 0, in particular, admits only
    // values with a(v) = 0. But this is only a legality test - several values
    // may pass it at once, and which one we actually take is settled by the
    // prime placement below.
    //
    // It remains to decide where the primes sit. Scanning pi from the right,
    // let g count the placed values whose prime lies to the right of v; since
    // the primes keep pi's order, those are always the g most recently placed
    // ones - the prefix picked[0..g-1]. Placing v then needs exactly
    // need = a(v) - larger_picked[v] of the smaller placed values to land in
    // that prefix. smaller_pos[v] is the vector of picked indices that hold a
    // value smaller than v; we want exactly need of them to fall inside the
    // prefix, so g has to sit past entry need-1 and at or before entry need:
    //
    //     g_lo = smaller_pos[v][need - 1] + 1,  g_hi = smaller_pos[v][need],
    //
    // with g_lo = 0 when need = 0 (nothing to include) and g_hi = k when
    // need = total_smaller (nothing left to exclude). The g only grows as we
    // move left, so it must also be above g_prev. Among the legal values we
    // keep the one whose forced g = max(g_lo, g_prev) is smallest, since a low
    // g leaves the most slack for the rest; ties go to the smallest value,
    // because picking v bumps larger_picked for every value below it, dragging
    // those toward the dead state larger_picked > a(.), so the smallest legal
    // value is the one that endangers the fewest others. A step with no legal
    // value means NO; otherwise f_r = n - g turns each cut back into a prime
    // count and the interleaving is emitted directly.

    for(int i = 0; i < n; i++) {
        if(a[i] < 0 || a[i] > n - 1) {
            cout << "NO\n";
            return;
        }
    }

    vector<int> picked;
    vector<bool> used(n + 1, false);
    vector<int> larger_picked(n + 1, 0);
    vector<vector<int>> smaller_pos(n + 1);
    vector<int> g(n, 0);
    int g_prev = 0;

    for(int k = 0; k < n; k++) {
        int best = -1, best_g = INT_MAX;
        for(int v = 1; v <= n; v++) {
            if(used[v]) {
                continue;
            }

            int need = a[v - 1] - larger_picked[v];
            int total_smaller = (int)smaller_pos[v].size();
            if(need < 0 || need > total_smaller) {
                continue;
            }

            int g_lo = (need == 0) ? 0 : smaller_pos[v][need - 1] + 1;
            int g_hi = (need == total_smaller) ? k : smaller_pos[v][need];

            int cur_g = max(g_lo, g_prev);
            if(cur_g > g_hi) {
                continue;
            }

            if(cur_g < best_g) {
                best = v;
                best_g = cur_g;
            }
        }

        if(best == -1) {
            cout << "NO\n";
            return;
        }

        picked.push_back(best);
        used[best] = true;
        g[k] = best_g;
        g_prev = best_g;
        for(int v = 1; v <= n; v++) {
            if(v < best) {
                larger_picked[v]++;
            } else if(v > best) {
                smaller_pos[v].push_back(k);
            }
        }
    }

    vector<int> pi(n + 1), f(n + 1);
    for(int r = 1; r <= n; r++) {
        pi[r] = picked[n - r];
        f[r] = n - g[n - r];
    }

    vector<int> seq;
    seq.reserve(2 * n);
    int next_primed = 1;
    for(int r = 1; r <= n; r++) {
        while(next_primed <= f[r]) {
            seq.push_back(-pi[next_primed]);
            next_primed++;
        }

        seq.push_back(pi[r]);
    }

    cout << "YES\n";
    cout << seq << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


def solve():
    # Read all integers from input.
    data = list(map(int, sys.stdin.read().split()))

    # First integer is n.
    n = data[0]

    # Next n integers are a[0], ..., a[n - 1].
    a = data[1:1 + n]

    # Each a[i] must be between 0 and n - 1.
    for x in a:
        if x < 0 or x > n - 1:
            print("NO")
            return

    # picked stores values of pi from right to left:
    # picked[0] = pi[n], picked[1] = pi[n - 1], ...
    picked = []

    # used[v] is True if value v is already placed.
    used = [False] * (n + 1)

    # larger_picked[v] = number of already picked values greater than v.
    larger_picked = [0] * (n + 1)

    # smaller_pos[v] stores indices in picked where values smaller than v appear.
    smaller_pos = [[] for _ in range(n + 1)]

    # g_values[k] stores chosen g when picked[k] is placed.
    g_values = [0] * n

    # g must be nondecreasing while building from right to left.
    g_prev = 0

    # Build the permutation from right to left.
    for k in range(n):
        # k is the number of already picked values.

        best = -1
        best_g = 10**18

        # Try all unused values as the next value.
        for v in range(1, n + 1):
            if used[v]:
                continue

            # Contributions from larger values already to the right are forced.
            # The remaining contribution must come from smaller values whose
            # primes are after v.
            need = a[v - 1] - larger_picked[v]

            # Number of already picked smaller values.
            total_smaller = len(smaller_pos[v])

            # need must be feasible.
            if need < 0 or need > total_smaller:
                continue

            # Find legal interval [g_lo, g_hi] for g.

            # If need == 0, no smaller value should be included,
            # so g can start from 0.
            # Otherwise, g must pass the (need - 1)-th smaller position.
            if need == 0:
                g_lo = 0
            else:
                g_lo = smaller_pos[v][need - 1] + 1

            # If need == total_smaller, all smaller values may be included,
            # so g can go up to k.
            # Otherwise, g must not pass the need-th smaller position.
            if need == total_smaller:
                g_hi = k
            else:
                g_hi = smaller_pos[v][need]

            # g cannot decrease.
            cur_g = max(g_lo, g_prev)

            # Candidate is invalid if the minimum possible g is too large.
            if cur_g > g_hi:
                continue

            # Greedy choice:
            # minimize cur_g.
            # Since v is scanned increasingly and we only update on strict
            # improvement, ties automatically choose the smallest v.
            if cur_g < best_g:
                best = v
                best_g = cur_g

        # No legal value means impossible.
        if best == -1:
            print("NO")
            return

        # Place best.
        picked.append(best)

        # Mark best as used.
        used[best] = True

        # Store chosen g.
        g_values[k] = best_g

        # Update g lower bound.
        g_prev = best_g

        # Update auxiliary information.
        for v in range(1, n + 1):
            if v < best:
                # best is greater than v and now lies to the right of v.
                larger_picked[v] += 1
            elif v > best:
                # best is smaller than v and appears at picked index k.
                smaller_pos[v].append(k)

    # Reconstruct pi[1..n] from picked.
    pi = [0] * (n + 1)

    # f[r] = number of primed objects that must appear before pi[r].
    f = [0] * (n + 1)

    for r in range(1, n + 1):
        # picked is reversed pi.
        pi[r] = picked[n - r]

        # If g primes are after pi[r], then n - g primes are before it.
        f[r] = n - g_values[n - r]

    # Construct final sequence.
    seq = []

    # next_primed is the next index in pi whose primed version is not output yet.
    next_primed = 1

    for r in range(1, n + 1):
        # Output all primed objects that should appear before pi[r].
        while next_primed <= f[r]:
            # Negative means primed.
            seq.append(-pi[next_primed])
            next_primed += 1

        # Output unprimed object.
        seq.append(pi[r])

    print("YES")
    print(*seq)


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed editorial

A bipermutation is an interleaving of two copies of one permutation `pi`: the primed copy and the unprimed copy, with the same relative order, and each primed element before its unprimed element.

Build `pi` from right to left. Suppose `v` is placed now and `k` values are already placed to its right.

For `a(v)`:

- every already placed value greater than `v` contributes via its unprimed object;
- some already placed values smaller than `v` contribute if their primed objects are still after `v`.

Maintain:

```text
larger_picked[v] = number of picked values greater than v
smaller_pos[v] = positions in picked of picked values smaller than v
```

Then:

```text
need = a[v] - larger_picked[v]
```

must be the number of smaller picked values whose primes are after `v`.

Let `g` be the number of picked values whose primes are after `v`. These are exactly the prefix `picked[0..g-1]`.

Using `smaller_pos[v]`, compute the interval of valid `g` values:

```text
g_lo = 0 if need == 0 else smaller_pos[v][need - 1] + 1
g_hi = k if need == total_smaller else smaller_pos[v][need]
```

Also `g` must be nondecreasing while moving left, so:

```text
g >= g_prev
```

Candidate `v` is valid if:

```text
max(g_lo, g_prev) <= g_hi
```

Greedily choose the valid `v` with smallest possible `g`; break ties by smaller `v`.

If no value is valid, print `NO`.

Otherwise reconstruct `pi` by reversing `picked`. If `g` primes are after `pi[r]`, then `n - g` primes are before it. Output primed objects in order before each unprimed object accordingly.

Complexity: `O(n^2)`.