<|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++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // Each a[i] counts some subset of the other n - 1 values.
    for (int i = 1; i <= n; i++) {
        if (a[i] < 0 || a[i] > n - 1) {
            cout << "NO\n";
            return 0;
        }
    }

    // picked stores pi from right to left:
    // picked[0] = pi[n], picked[1] = pi[n - 1], ...
    vector<int> picked;
    picked.reserve(n);

    vector<bool> used(n + 1, false);

    // larger_picked[v] = number of already picked values greater than v.
    vector<int> larger_picked(n + 1, 0);

    // smaller_pos[v] = positions in picked where picked value is smaller than v.
    vector<vector<int>> smaller_pos(n + 1);

    // g_values[k] stores chosen g for picked[k].
    vector<int> g_values(n, 0);

    // g must be nondecreasing while constructing from right to left.
    int g_prev = 0;

    for (int k = 0; k < n; k++) {
        // k = number of already picked values.

        int best = -1;
        int best_g = INT_MAX;

        // Try every unused value as the next element of pi from the right.
        for (int v = 1; v <= n; v++) {
            if (used[v]) {
                continue;
            }

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

            // Number of already picked values smaller than v.
            int total_smaller = (int)smaller_pos[v].size();

            // need must be exactly the number of smaller picked values
            // whose primes will be after v.
            if (need < 0 || need > total_smaller) {
                continue;
            }

            // We need exactly 'need' positions from smaller_pos[v]
            // to be strictly less than g.

            int g_lo;
            if (need == 0) {
                g_lo = 0;
            } else {
                g_lo = smaller_pos[v][need - 1] + 1;
            }

            int g_hi;
            if (need == total_smaller) {
                g_hi = k;
            } else {
                g_hi = smaller_pos[v][need];
            }

            // g cannot decrease compared to previous steps.
            int cur_g = max(g_lo, g_prev);

            // Candidate is feasible if cur_g still lies in the allowed interval.
            if (cur_g > g_hi) {
                continue;
            }

            // Greedy choice:
            // minimize cur_g; ties are resolved by smaller v because
            // we scan v increasingly and update only on strict improvement.
            if (cur_g < best_g) {
                best_g = cur_g;
                best = v;
            }
        }

        // No legal value can be placed here.
        if (best == -1) {
            cout << "NO\n";
            return 0;
        }

        // Place the chosen value.
        picked.push_back(best);
        used[best] = true;
        g_values[k] = best_g;
        g_prev = best_g;

        // Update helper arrays for remaining values.
        for (int v = 1; v <= n; v++) {
            if (used[v]) {
                continue;
            }

            if (v < best) {
                // best is greater than v and is now to the right of v.
                larger_picked[v]++;
            } else if (v > best) {
                // best is smaller than v and appears at position k in picked.
                smaller_pos[v].push_back(k);
            }
        }
    }

    // Reconstruct pi[1..n].
    vector<int> pi(n + 1);

    // f[r] = number of primed objects that must appear before pi[r].
    vector<int> f(n + 1);

    for (int r = 1; r <= n; r++) {
        // 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];
    }

    vector<int> answer;
    answer.reserve(2 * n);

    // next_primed is the next index in pi whose primed copy is not output yet.
    int next_primed = 1;

    for (int r = 1; r <= n; r++) {
        // Output all primed objects that should appear before pi[r].
        while (next_primed <= f[r]) {
            answer.push_back(-pi[next_primed]);
            next_primed++;
        }

        // Output unprimed pi[r].
        answer.push_back(pi[r]);
    }

    cout << "YES\n";
    for (int i = 0; i < (int)answer.size(); i++) {
        if (i) cout << ' ';
        cout << answer[i];
    }
    cout << '\n';

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