The permutations that can be reached are characterized as follows: For each value \(v\), there is an interval \([l_v,r_v]\) that satisfies the following conditions.

• The position of \(v\) is within \([l_v,r_v]\) for all \(v\), such a permutation can be created.
• \([l_i,r_i]\) forms the structure of a rooted tree. (The larger \(v\) is, the closer it is to the root.)

Let’s create the proof and algorithm at the same time.

For convenience, let’s assume that there is an interval \([i,i]\) for \(i=1,\cdots,N\) at the beginning. We will find \([l_v,r_v]\) in ascending order of \(v\).

Let’s say we have found it for up to \(v=m\). Considering the intervals existing at this point, several trees have been formed. Here, the following condition holds for each tree.

Let the root of the tree be the interval \([L,R]\). Consider how we can rearrange the values within \([L,R]\) using only operations that keep them within \([L,R]\). For values less than or equal to \(m\), we have determined \([l_i,r_i]\), and they can only exist within this interval. Conversely, any arrangement that satisfies these conditions can be achieved. In particular, values greater than \(m\) can be rearranged as we like.

We will confirm this condition inductively later.

Now, in such a situation, let’s find the interval in which \(v=m+1\) can exist. First, take the interval \([L,R]\) corresponding to the root of the tree to which \(v\) belongs. The problem is how far we can extend these \(L\) and \(R\) to the left and right.

For example, consider \(L\). The most desirable state to move \(v\) across \(L\) is as follows:

For values whose position is \(L\) or to the right of it:

• \(v\) is as close to \(L\) as possible.
• On top of that, values less than or equal to \(m\) are as close to \(L\) as possible.

For values whose position is to the left of \(L\):

• Only one value greater than \(m+1\) is close to \(L\).
• On top of that, values less than or equal to \(m\) are as close to \(L\) as possible.

In this situation, if a swap across \(L\) can be made, then \(v\) can enter the tree on the left. Conversely, if a swap cannot be made in this way, \(L\) cannot be made any smaller.

This situation, as mentioned, can be further organized. For values less than or equal to \(m\), the interval has already been determined, but from the way \(L\) is taken, this interval does not cross \(L\). Therefore, “getting as close to \(L\) as possible while being to the right of \(L\)” means “placing it as far to the left as possible”. The same applies to the left of \(L\).

Therefore, the distribution of the positions of values less than or equal to \(m\) can be determined as follows. First, ignoring values greater than or equal to \(m+1\), get as close to \(L\) as possible. As mentioned above, this can be done by greedily placing values on the left/right.

To cross \(L\), we wanted \(v\) to get closer to \(L\). In fact, it turns out that \(v\) can be placed in the “leftmost possible position for \(v\) to exist from the information so far”. The “leftmost possible position for \(v\) to exist from the information so far” is the closest unused position to \(L\) that is at or to the right of \(L\) assuming that values less than or equal to \(m\) are placed as far to the “right” as possible. It is obviously most desirable to place it here, and it can be placed here because of the assumption that the values within the tree can be freely swapped.

By the way, since values less than or equal to \(m\) are placed as far to the “left” as possible, some adjustments are necessary to place \(v\). For example, it would be a problem if a value less than or equal to \(m\) is already in the place where we want to place \(v\). This can be easily handled by simply shifting the positions of values less than or equal to \(m\) appropriately and making room for \(v\). Also, when this placement is made, the position of the “leftmost value to the right of \(L\) greater than \(v\)” can be easily found. It is the second closest unused position to \(L\) that is at or to the right of \(L\) assuming that values less than or equal to \(m\) are placed as far to the “left” as possible.

The situation on the left side of \(L\) can be determined in the same way. Therefore, in the end, in order to check whether a swap across \(L\) can be made, it is sufficient to keep the unused positions assuming that values less than or equal to \(m\) are placed as far to the left/right as possible. This can be held in a set, and the only necessary operations are lower_bound and increment/decrement of iterators.

The interval obtained by extending \(L\) and \(R\) as far to the left and right as possible will be \([l_v,r_v]\). Here, it can also be seen that the values within the tree can be freely swapped.

Implementing the above solves this problem in \(O(N \log N)\) time.

Sample Implementation