Rae Taylor and Trees (easy version)

Let $pos[x]$ be the position of value $x$ in the permutation.

The condition for an edge is:

• if $u<v$, then $u$ must appear before $v$ in $p$;
• equivalently, $pos[u] < pos[v]$.

So define an auxiliary graph $G$ with vertices $1,2,\dots,n$, where we put an edge between $u$ and $v$ exactly when that edge is legal.

Now the whole tree part is basically bait. A tree satisfying the rule exists iff $G$ is connected, because:

• if such a tree exists, then obviously $G$ is connected;
• if $G$ is connected, take any spanning tree of $G$.

So we only need to test whether this graph is connected.

Rewriting the graph

Look at labels in increasing order: $1,2,\dots,n$.

Let

$a_i = pos[i].$

For $i<j$, edge $(i,j)$ exists iff

$a_i < a_j.$

So edges are exactly increasing pairs in the array $a$.

When is the graph disconnected?

Suppose we split labels after $k$:

$\{1,2,\dots,k\}\quad\text{and}\quad\{k+1,k+2,\dots,n\}.$

An edge across this split would need some $i\le k$ and $j>k$ with:

$a_i < a_j.$

So there is no edge across the split iff every value on the left is larger than every value on the right:

$\min_{i\le k} a_i > \max_{j>k} a_j.$

If this happens, the graph is disconnected immediately. No spanning tree. No magic. The tree is dead.

Why checking only these prefix/suffix splits is enough

A disconnected graph has at least two connected components. Take the component containing label $1$, and let $k$ be the largest label in that component.

If $k<n$, then no vertex $j>k$ can have an edge to any vertex in this component. In particular, since $1$ through $k$ can be considered as a separated left block at the first place where connectivity cannot continue, there must be a split where every left position is after every right position. In terms of $a$, that is exactly:

$prefMin[k] > suffMax[k+1].$

Another way to see it: if for every $k<n$ there exists some crossing increasing pair, then every prefix has at least one legal edge going to the suffix. That prevents the labels from being separated into multiple connected chunks, so all vertices merge into one connected graph.

So the whole problem reduces to finding whether such a “reverse wall” exists.

Algorithm

For each test case:

1. Read permutation $p$.
2. Build $pos[x]$.
3. Compute:
   • $prefMin[i] = \min(pos[1],\dots,pos[i])$,
   • $suffMax[i] = \max(pos[i],\dots,pos[n])$.
4. For every $k=1$ to $n-1$, if

$prefMin[k] > suffMax[k+1],$

then answer No.

Otherwise answer Yes.

Complexity

Each test case is $O(n)$.

Across all test cases, this is $O(\sum n)$, which easily fits. The constraints are not the boss fight here; the trick is realizing the “tree” is just connectivity in a very specific graph.