When there are adjacent equal values on the circumference, we may combine them without changing the answer.

Additionally, if a \(1\) and a \(2\) are adjacent, erasing the \(1\) by connecting them does not change the answer. Similarly, if a \(3\) and a \(4\) are adjacent, the \(4\) may be erased.

We define normalization as the process of repeating the above operations as many times as possible.

Any valid tree always has an edge that satisfies the following conditions.

• Its endpoints are adjacent on the circumference.
• One of its endpoints is a leaf.

Thus, we can see that any valid tree can be obtained by repeating the following operation.

• Choose two vertices adjacent on the circumference that can be connected.
• Connect them.
• Choose one of them as a leaf to erase it from the circumference.

Consider this series of actions: on a normalized state, perform the above operation once and then normalize it again.

In a normalized tree, one may only connect a pair of vertices with \(2\) and \(3\) written on them. Here, assume that a \(2\) is erased as a leaf. If the nearby values on the circumference are \(\cdots,4,2,3,\cdots\), erasing the \(2\) makes the \(4\) and \(3\) adjacent, and then \(4\) will be erased by normalization. As a whole, the \(4\) and \(2\) will be erased. Similarly, if the nearby values on the circumference are \(\cdots,3,2,3,\cdots\), the \(3\) and \(2\) will be erased.

If we also consider the case of erasing a \(3\), we can see that this series of actions erases a pair of vertices that is \((2,3)\), \((1,3)\), or \((2,4)\).

If one can repeat this process so that there will be only \(2\)s and \(3\)s on the circumference, a valid tree can be constructed.

Therefore, the following necessary condition can be derived.

• \(C_2>C_4\) and \(C_3>C_1\) must hold, where \(C_1,C_2,C_3,C_4\) are the numbers of \(1,2,3,4\) in \(A\), respectively.

We can also see that this condition is also sufficient. This is because when \(1\) or \(4\) remain on the circumference, one can always perform the operation to erase \((1,3)\) or \((2,4)\).

A direct implementation of this criterion solves the problem in \(O(N)\) time.

Sample code (c++)