<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

279. Bipermutations
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



A bipermutation of order n is a linear order of 2n objects 1, 1', 2, 2' ... n, n'  satisfying the following conditions:

For each i such that 1≤ i≤ n holds i <. j.
For each i and j such that 1≤ i,j≤ n holds i' < j' <=> i <. j.

Let  bij = { 
    j' if j < i
    j  if j > i
}

(bii is undefined). Let a(i) be the number of such j that i <. bij . You are given integers a1,a2,..., an. You have to find any bipermutation such that a(i)=ai for all i.

Input
The first line of the input contains single integer n (1≤ n≤ 1000). The next line contains the numbers a1,...,an.

Output
If there is no solution, the only line of the output must contain single word 'NO' (without quotes). Otherwise the first line of the output must contain single word 'YES' (without quotes); the rest of the output must contain the objects ordered with respect to the bipermutation ( is output as -i).

Example(s)
sample input
sample output
9
2 0 3 0 4 8 1 5 4
YES
-6 -8 -9 6 -5 -3 8 9 -7 5 -1 -4 3 7 -2 1 4 2 



Hint: If i <. bij and j <. bjk, then i <. bik.

Novosibirsk SU Contest #2, by Novosibirsk Team #1

<|response|>
## 1. Abridged problem statement

We have `2n` objects:

```text
1, 1', 2, 2', ..., n, n'
```

A valid bipermutation is a linear ordering such that:

1. For every `i`, the primed object `i'` is before the unprimed object `i`.
2. The relative order of primed objects is the same as the relative order of unprimed objects.

For `i != j`, define:

```text
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, a2, ..., an`, construct any valid bipermutation with these values, or report that none exists.

Unprimed `i` is printed as `i`, primed `i'` as `-i`.

Constraints:

```text
1 <= n <= 1000
```

---

## 2. Key observations needed to solve the problem

### Observation 1: A bipermutation is an interleaving of two equal-order copies

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

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

The unprimed objects appear in this order:

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

The primed objects also appear in this order:

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

A valid bipermutation is just an interleaving of those two copies, with every `pi[r]'` before `pi[r]`.

---

### Observation 2: Contribution to `a(v)`

Suppose `v = pi[r]`.

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

So `j` contributes to `a(v)` iff unprimed `j` is to the right of `v` in `pi`.

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

So `j` contributes to `a(v)` iff `j'` is after unprimed `v`.

Therefore:

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

This is the central formula.

---

### Observation 3: Build `pi` from right to left

We construct the unprimed permutation from the end.

Let:

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

At some step, suppose we have already picked `k` values. Those values are exactly the suffix of `pi`, i.e. the values to the right of the current candidate.

For an unused value `v`:

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

These values definitely contribute to `a(v)`.

The remaining required contribution is:

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

This must come from smaller already-picked values whose primed objects are placed after `v`.

---

### Observation 4: Describing prime positions using one number `g`

When placing a new value `v`, define:

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

Because the primed order is the same as the unprimed order, these values must be exactly:

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

That is, a prefix of `picked`.

For each value `v`, maintain:

```text
smaller_pos[v]
```

This stores the indices in `picked` where values smaller than `v` appear.

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

If:

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

then valid `g` values satisfy:

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

with boundary cases:

```text
need = 0  => g can start from 0
need = m  => g can go up to k
```

So:

```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
```

A candidate `v` is legal iff:

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

---

### Observation 5: Greedy choice

At every step, among all legal unused values, choose the candidate with the smallest possible current `g`.

If there is a tie, choose the smallest value.

Reason:

- Smaller `g` leaves more flexibility for future positions.
- Future `g` values must be nondecreasing.
- Picking a smaller value is safer because it increases `larger_picked` for fewer remaining values.

If no candidate is legal at some step, no solution exists.

---

## 3. Full solution approach based on the observations

We maintain:

```text
picked
```

The suffix of `pi`, stored from right to left.

```text
used[v]
```

Whether value `v` has already been placed.

```text
larger_picked[v]
```

Number of already picked values greater than `v`.

```text
smaller_pos[v]
```

Positions inside `picked` where already picked values smaller than `v` appear.

```text
g_values[k]
```

The chosen `g` value when `picked[k]` was placed.

Algorithm:

1. Validate that every `a[i]` is between `0` and `n - 1`.
2. Build `pi` from right to left.
3. At step `k`, try every unused value `v`.
4. Compute:

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

5. If `need` is not between `0` and the number of smaller picked values, skip `v`.
6. Compute the legal interval `[g_lo, g_hi]`.
7. Apply monotonicity:

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

8. If `cur_g <= g_hi`, then `v` is a legal candidate.
9. Pick the legal candidate with minimum `cur_g`, breaking ties by smaller `v`.
10. If no candidate exists, print `NO`.
11. Otherwise, store the chosen value and update helper arrays.
12. After all values are picked, reverse `picked` to get `pi`.
13. Reconstruct the final bipermutation.

For reconstruction:

If `g` primes are after `pi[r]`, then:

```text
n - g
```

primed objects are before `pi[r]`.

Let:

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

Before outputting unprimed `pi[r]`, output all not-yet-output primed objects up to `pi[f[r]]'`.

Complexity:

```text
Time:   O(n^2)
Memory: O(n^2)
```

This is fine for `n <= 1000`.

---

## 4. 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;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.read().split()))

    n = data[0]
    raw_a = data[1:1 + n]

    # Use 1-indexing for convenience.
    a = [0] + raw_a

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

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

    used = [False] * (n + 1)

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

    # smaller_pos[v] = positions in picked where picked value is smaller than v.
    smaller_pos = [[] for _ in range(n + 1)]

    # g_values[k] stores chosen g for picked[k].
    g_values = [0] * n

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

    for k in range(n):
        # k = number of already picked values.

        best = -1
        best_g = 10**18

        # Try every unused value.
        for v in range(1, n + 1):
            if used[v]:
                continue

            # Contributions already forced by larger values to the right.
            need = a[v] - larger_picked[v]

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

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

            # Compute legal interval [g_lo, g_hi].
            #
            # We need exactly 'need' positions from smaller_pos[v]
            # to be strictly less than g.

            if need == 0:
                g_lo = 0
            else:
                g_lo = smaller_pos[v][need - 1] + 1

            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 even the smallest possible g is too large.
            if cur_g > g_hi:
                continue

            # Greedy choice:
            # minimize cur_g; ties automatically go to smaller v because
            # v is scanned increasingly and we only update on strict improvement.
            if cur_g < best_g:
                best_g = cur_g
                best = v

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

        # Place the chosen value.
        picked.append(best)
        used[best] = True
        g_values[k] = best_g
        g_prev = best_g

        # Update helper arrays for remaining values.
        for v in range(1, n + 1):
            if used[v]:
                continue

            if v < best:
                # best is greater than v and is now to the right of v.
                larger_picked[v] += 1
            elif v > best:
                # best is smaller than v and appears at position k in picked.
                smaller_pos[v].append(k)

    # Reconstruct pi[1..n].
    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 this object, n - g primes are before it.
        f[r] = n - g_values[n - r]

    answer = []

    # next_primed is the next index in pi whose primed copy 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]:
            answer.append(-pi[next_primed])
            next_primed += 1

        # Output unprimed pi[r].
        answer.append(pi[r])

    print("YES")
    print(*answer)


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