A rail yard receives n containers lined up on a single track, each stamped with an integer ID. Before departure, the containers must be arranged into a required order, also given as a sequence of n IDs. The yard crane can pick any contiguous block of containers currently on the track and reverse the order of that block in place; this operation can be performed any number of times, on any contiguous blocks, in any order. Determine whether the crane can transform the current line of containers into the required order.
The first line contains one integer n, the number of containers. The second line contains n integers arr[1], ..., arr[n], the current order of container IDs. The third line contains n integers target[1], ..., target[n], the required order of container IDs.
Print "YES" if the crane can rearrange the containers into the required order, or "NO" otherwise.
Example 1
Input
4 3 1 2 3 1 3 3 2
Expected
YES
Explanation
Sorting both sequences gives [1,2,3,3] for the current order and [1,2,3,3] for the required order — the same multiset of IDs. Since reversing contiguous blocks repeatedly can realize any rearrangement of a sequence, the crane can reach the required order, so the answer is YES.
Example 2
Input
3 5 6 7 5 6 8
Expected
NO
Explanation
The current containers are {5,6,7} while the required order needs {5,6,8}; container 7 has no counterpart in the target and 8 never appears on the track. Since reversals only reorder existing containers and never change their IDs, no sequence of reversals can produce the required order, so the answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →