Siga ta Kymata

Think of every permutation element as a point $(i,p_i)$.

An operation $(l,r)$ paints position $i$ exactly when

$$l<i<r$$

and

$$\min(p_l,p_r)<p_i<\max(p_l,p_r).$$

So we are painting points inside an open rectangle whose opposite corners are two existing permutation points.

The impossible border

Some points can never be painted:

• $i=1$ cannot be painted because there is no $l<i$.
• $i=n$ cannot be painted because there is no $r>i$.
• $p_i=1$ cannot be strictly between two permutation values.
• $p_i=n$ cannot be strictly between two permutation values.

So if $x_i=1$ for any of those positions, print -1. No clever trick saves it. The rectangle is open, and the border is cooked.

Now the nice part: every other point can be covered using one fixed set of at most five operations.

The five operations

Let

$$a=\operatorname{pos}(1),\qquad b=\operatorname{pos}(n).$$

Use these candidate operations:

$$(a,b),\quad (1,a),\quad (1,b),\quad (n,a),\quad (n,b).$$

Skip invalid operations where both endpoints are the same. Normalize the order so $l<r$.

There are at most $5$ operations, exactly matching the limit.

Why these cover everything useful

Take any needed position $i$ such that

$$1<i<n \quad\text{and}\quad 1<p_i<n.$$

We prove one of the five operations paints it.

There are three cases based on where $i$ sits compared to $a$ and $b$.

Case 1: $i$ is between $a$ and $b$

Operation $(a,b)$ has endpoint values $1$ and $n$. Since $1<p_i<n$, the value condition holds. Since $i$ is between $a$ and $b$, the index condition holds too.

So $(a,b)$ paints $i$.

Case 2: $i$ is left of both $a$ and $b$

Then $1<i<a$ and $1<i<b$, because $i$ is not index $1$.

Compare $p_i$ with $p_1$.

If $p_i<p_1$, then operation $(1,a)$ works: its endpoint values are $p_1$ and $1$, and

$$1<p_i<p_1.$$

If $p_i>p_1$, then operation $(1,b)$ works: its endpoint values are $p_1$ and $n$, and

$$p_1<p_i<n.$$

Since $i\ne 1$, we have $p_i\ne p_1$, so exactly one of those comparisons happens.

Case 3: $i$ is right of both $a$ and $b$

This is symmetric. Now $a<i<n$ and $b<i<n$.

Compare $p_i$ with $p_n$.

If $p_i<p_n$, then operation $(a,n)$ works because its endpoint values are $1$ and $p_n$.

If $p_i>p_n$, then operation $(b,n)$ works because its endpoint values are $n$ and $p_n$.

Again, $i\ne n$, so $p_i\ne p_n$.

That proves every non-border position can be painted by these five operations.

Algorithm

For each test case:

1. Read $p$ and $x$.
2. Find positions of values $1$ and $n$.
3. If any required position has index $1$ or $n$, or value $1$ or $n$, print -1.
4. If there are no required positions, print 0.
5. Otherwise output the valid unique operations among: $$(a,b),(1,a),(1,b),(n,a),(n,b).$$

We do not care if these operations paint extra zeroes. The statement explicitly allows that, so don't do pointless gymnastics.

Correctness proof

First, if the algorithm prints -1, then some required position is on the border: index $1$, index $n$, value $1$, or value $n$. Such a position cannot satisfy the strict index and value inequalities of any operation, so no valid answer exists.

Otherwise, every required position $i$ satisfies $1<i<n$ and $1<p_i<n$.

Let $a=\operatorname{pos}(1)$ and $b=\operatorname{pos}(n)$. For any required position $i$:

• If $i$ lies between $a$ and $b$, operation $(a,b)$ paints it.
• If $i$ lies left of both $a$ and $b$, then either $(1,a)$ or $(1,b)$ paints it depending on whether $p_i<p_1$ or $p_i>p_1$.
• If $i$ lies right of both $a$ and $b$, then either $(a,n)$ or $(b,n)$ paints it depending on whether $p_i<p_n$ or $p_i>p_n$.

These are exactly among the five operations the algorithm outputs. Therefore every required position is painted.

The algorithm outputs at most five valid operations, so the produced answer satisfies the statement.

Complexity

Each test case is processed in $O(n)$ time and $O(n)$ memory. The total input size is $2\cdot 10^5$, so this is easily fast enough.