Hints: Definitely Larger

Process indices from $N - 1$ down to $0$. When handling $i$, every index $j > i$ is already assigned a provisional value Q[j] (a compressed rank, not the final permutation yet).

Collect Q[j] for all $j > i$ with $p_j > p_i$, sort these values in nonincreasing order into vals. If $d_i$ exceeds the number of such indices, print $-1$.

Set a new rank nval: if $d_i$ equals the size of vals, take nval = 0 (largest rank among processed indices). Otherwise set nval to $\text{vals}[d_i] + 1$, i.e. just below the $d_i$-th largest among the collected ranks.

Before writing Q[i] = nval, bump every existing Q value that is at least nval upward by $1$. This simulates inserting $i$ into a total order without storing the whole list: ranks stay distinct integers.

After the sweep, output Q[i] + 1 for each position: the relative order encoded by Q turns into a concrete permutation of $1..N$.

Focus on a fixed index $i$.
Its condition only depends on indices $j$ such that:

• $j > i$,
• $p_j > p_i$,
• and whether $q_j > q_i$.

So if we process indices from right to left, then when handling $i$, all relevant $j$ are already processed.

Answer to Hint 1:
Let

$$ S_i = \{j \mid j>i,\ p_j>p_i\}. $$

We need exactly $d_i$ elements of $S_i$ to have larger $q$ than $q_i$.

If $d_i > |S_i|$, answer is immediately impossible.

Answer to Hint 2:
Think only about relative order of $q$, not exact values.

Maintain the already processed suffix indices in a list sorted by decreasing $q$ (front = largest $q$).

When inserting index $i$, you only need to control how many elements of $S_i$ are placed before it in this list.

Answer to Hint 3:
Suppose you scan the current list from left to right and count elements with $p_j > p_i$.

To make exactly $d_i$ such elements larger than $q_i$, insert $i$:

• after the $d_i$-th qualifying element (if $d_i > 0$),
• or at the very front (if $d_i = 0$).

This guarantees precisely $d_i$ qualifying indices stay before $i$.

Answer to Hint 4:
Why does this remain valid later?

Later insertions are for indices $k < i$.
They are never in $S_i$ because $S_i$ requires $j > i$.

So future operations cannot change how many valid $j$ dominate index $i$.

Answer to Hint 5:
After all insertions, you have a full order of indices by decreasing $q$.

Now assign actual permutation values:

• first index in the list gets $q=n$,
• second gets $q=n-1$,
• …
• last gets $q=1$.

Only relative order matters, so this produces a valid permutation.

Complexity check:

• For each $i$, you scan the current list (size up to $n$) a constant number of times.
• Total is $O(n^2)$ per test case.

Given $\sum n \le 5000$, this is easily fast enough.