Definitely Larger

Observation 1: $q$ is just an order

The actual values $1..n$ inside $q$ do not matter. Only comparisons like $q_j>q_i$ matter. So forget the numbers for a second and build an order ord of indices from smallest $q$ to largest $q$.

Then $j$ dominates $i$ exactly when $j>i$, $p_j>p_i$, and $j$ is placed after $i$ in ord.

For each $i$, let $c_i$ be the number of indices $j>i$ with $p_j>p_i$. If $d_i>c_i$, the answer is impossible. There simply are not enough candidates.

Observation 2: right-to-left is the natural direction

When you place index $i$, every possible dominator of $i$ is already in the suffix $i+1, i+2, ..., n$. Even better, once some index $k$ is already placed, it is frozen forever: later we only insert indices smaller than $k$, and such indices can never dominate $k$ because domination needs $j>k$.

So processing $i=n, n-1, ..., 1$ is the obvious greedy.

The key lemma

Suppose we already built ord for the suffix. Look only at the processed indices with $p_j>p_i$. In their current order, call them

$b_1, b_2, ..., b_{c_i}.$

Index $i$ wants exactly $d_i$ of them after it, so it wants exactly

$e_i = c_i - d_i$

of them before it.

Now comes the whole trick: these relevant indices create exactly $c_i+1$ slots:

• before $b_1$,
• between consecutive relevant indices,
• after $b_{c_i}$.

If you insert $i$ into slot number $k$, then exactly $k$ relevant indices are before it. So every value $k=0,1,...,c_i$ is achievable.

That means the condition that $d_i$ is at most $c_i$ is not only necessary. It is also sufficient. Yep, the global consistency nightmare evaporates into one boring local bound.

Greedy construction

Maintain ord = processed indices in increasing $q$.

For $i=n, n-1, ..., 1$:

1. Collect the positions in ord whose $p$ is larger than $p_i$.
2. Let $c$ be how many there are.
3. If $d_i>c$, print -1.
4. Otherwise compute

$e = c - d_i$

and insert $i$ right after the $e$-th collected position. If $e=0$, insert at the front.

Any slot with the right count works; this is just a clean canonical choice.

After all insertions, assign

$q_{ord[pos]} = pos + 1.$

Since ord is from smallest $q$ to largest $q$, this is a valid permutation.

Why it works

Use induction on decreasing $i$.

Invariant after processing the suffix $i+1, i+2, ..., n$:

• ord is the correct increasing-$q$ order of that suffix;
• every processed index already has exactly its required number of dominators.

Base case: the empty suffix. Trivially true.

Induction step: for the current index $i$, the only possible dominators are already processed, and among them only the ones with $p_j>p_i$ matter. There are exactly $c_i$ of them. By the slot lemma, we can place $i$ so that exactly $e_i=c_i-d_i$ of them are before it, hence exactly $d_i$ of them are after it. So $i$ becomes correct.

Previously processed indices stay correct, because the new index $i$ is smaller than all of them, and a dominator must have larger index. So no old answer changes.

Thus the invariant survives, and when the process ends, every index is correct.

If the algorithm rejects, it found some $i$ with $d_i>c_i$, which is obviously impossible. So the algorithm is correct in both directions.

Complexity

For each $i$, we scan the current ord and do one vector insertion. That is

$O(n^2)$

time and $O(n)$ memory.

Since the total $n$ over all test cases is at most $5000$, this passes comfortably. Dragging heavier machinery here would just be algorithm cosplay.