Overview

Determine whether it is possible to reverse exactly one contiguous subarray of the current permutation \(p\) to obtain the target permutation \(q\).
The key idea is to look at where each element of \(q\) was located in \(p\).

Analysis

We record the position of each value in \(p\).
That is,

\[ \mathrm{pos}[x] = \text{position of } x \text{ in } p \]

Then, we define the position where \(q_i\) was located in \(p\) as

\[ a_i = \mathrm{pos}[q_i] \]

For example, if

\[ p = [1, 2, 3, 4, 5, 6] \]

and we reverse the interval \([2, 5]\), we get

\[ q = [1, 5, 4, 3, 2, 6] \]

At this point, looking at where each element of \(q\) was originally located in \(p\), we get

\[ a = [1, 5, 4, 3, 2, 6] \]

In other words, for the non-reversed parts \(a_i = i\), and within the reversed interval the positions are in reverse order.

If the interval \([L, R]\) is reversed, the following holds:

• For positions where \(i < L\) or \(i > R\), there is no change, so \(a_i = i\)
• For positions where \(L \leq i \leq R\), the reversal occurs, so \(a_i = L + R - i\)

Therefore, \(a_i\) must have the following form:

unchanged / contiguous reversed interval / unchanged

Why the naive approach is too slow

If we try all intervals \([L, R]\), there are \(O(N^2)\) ways to choose the interval.
Furthermore, comparing the array after reversal for each interval takes \(O(N)\), resulting in \(O(N^3)\) overall.

Since \(N \leq 10^6\), this approach is too slow.

Key Insight

Suppose we find the first position where \(a_i \neq i\).
This position must be the left endpoint \(L\) of the reversed interval.

Moreover, at that point

\[ a_L = R \]

This is because, after reversal, position \(L\) contains the element that was originally at position \(R\).

In other words, once we find the first mismatch, the reversed interval \([L, R]\) is uniquely determined.
After that, we only need to verify that the elements within the interval are correctly reversed and that elements outside the interval remain unchanged.

Algorithm

First, record the position of each value in \(p\).

pos[p_i] = i

Note that the implementation uses 0-based indexing.

Next, scan \(q\) from left to right.

For each position \(i\), compute:

a = pos[q_i]

If we haven’t found the reversed interval yet:

• If \(a = i\), the position matches, so we continue.
• If \(a \neq i\), this is the left endpoint \(l\) of the reversed interval.
  • The right endpoint is determined as \(r = a\).
  • If \(r \leq l\), it is impossible.

After finding the reversed interval:

• While \(i \leq r\), we are inside the reversed interval.
  • If correctly reversed, the following must hold:

\[ a = l + r - i \]

• If \(i > r\), we are outside the reversed interval.
  • Therefore, the following must hold:

\[ a = i \]

If all conditions are satisfied until the end, output Yes. If any condition is violated along the way, output No.

Note that the case where \(p = q\) from the beginning is also Yes.
This is because the problem allows reversal with \(L = R\), which is an operation that changes nothing.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

Since \(N\) can be as large as \(10^6\), fast input processing is used.

Also, there is no need to store the entire array \(q\).
We read \(q_i\) one at a time and check pos[q_i] on the fly to make the determination.

In the code, 0-based indexing is used, so the condition inside the reversed interval is:

a == l + r - i

Source Code

import sys

def main():
    data = sys.stdin.buffer.read() + b' '
    idx = 0

    def next_int():
        nonlocal idx
        while data[idx] <= 32:
            idx += 1
        x = 0
        while data[idx] > 32:
            x = x * 10 + data[idx] - 48
            idx += 1
        return x

    n = next_int()

    pos = [0] * (n + 1)
    for i in range(n):
        pos[next_int()] = i

    l = -1
    r = -1
    ok = True

    for i in range(n):
        a = pos[next_int()]

        if l == -1:
            if a != i:
                l = i
                r = a
                if r <= l:
                    ok = False
                    break
        elif i <= r:
            if a != l + r - i:
                ok = False
                break
        else:
            if a != i:
                ok = False
                break

    print("Yes" if ok else "No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.