/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正の整数からなる長さ N の列 A=(A _ 1,A _ 2,\ldots,A _ N),B=(B _ 1,B _ 2,\ldots,B _ N) が与えられます。
列 A に対して次の操作をちょうど \mathbf{1} 回だけ行います。
- A の要素を一つ選んで取り出し、残った列の好きな位置に挿入する。より厳密には、以下の 2 つの操作を順に行う。
- 1\le i\le N を満たす整数 i を一つ選び、長さ N-1 の列 X=(X _ 1,X _ 2,\ldots,X _ {N-1}) を (A _ 1,A _ 2,\ldots,A _ {i-1},A _ {i+1},A _ {i+2},\ldots,A _ N) とし、整数 Y を A _ i とする。
- 1\le j\le N を満たす整数 j を一つ選び、長さ N の列 (X _ 1,X _ 2,\ldots,X _ {j-1},Y,X _ j,X _ {j+1},\ldots,X _ {N-1}) を新たな A とする。
要素を挿入するとき、列の左端や右端に挿入してもよいことに注意してください。
操作ののち A を B と一致させることができるか判定してください。
制約
- 1\le N\le2\times10 ^ 5
- 1\le A _ i\le N\ (1\le i\le N)
- 1\le B _ i\le N\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \ldots A _ N B _ 1 B _ 2 \ldots B _ N
出力
操作をちょうど 1 回行って A と B を一致させられる場合 Yes と、そうでない場合 No と一行に出力せよ。
入力例 1
6 1 4 1 4 2 1 1 4 1 1 4 2
出力例 1
Yes
例えば、A _ 6 を取り出し、残った列の先頭から 3 項目と 4 項目の間に挿入することで、操作を行ったあとの A を (1,4,1,1,4,2) とすることができます。
よって、Yes と出力してください。
入力例 2
2 1 1 1 2
出力例 2
No
A にどのような操作を行っても B と一致させることはできません。
入力例 3
3 1 2 3 1 2 3
出力例 3
Yes
取り出した要素を、もともとあった位置に挿入しても構いません。
入力例 4
30 25 11 21 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 18 16 16 20 16 25 11 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 21 18 16 16 20 16
出力例 4
Yes
Score : 300 points
Problem Statement
You are given sequences A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ N) of length N consisting of positive integers.
The following operation is performed on the sequence A exactly once.
- Choose one element of A, take it out, and insert it at any position in the remaining sequence. More formally, perform the following two steps in order.
- Choose an integer i satisfying 1\le i\le N, let the sequence X=(X _ 1,X _ 2,\ldots,X _ {N-1}) of length N-1 be (A _ 1,A _ 2,\ldots,A _ {i-1},A _ {i+1},A _ {i+2},\ldots,A _ N), and let the integer Y be A _ i.
- Choose an integer j satisfying 1\le j\le N, and let the sequence (X _ 1,X _ 2,\ldots,X _ {j-1},Y,X _ j,X _ {j+1},\ldots,X _ {N-1}) of length N be the new A.
Note that the element may be inserted at the left end or the right end of the sequence.
Determine whether it is possible to make A equal to B after the operation.
Constraints
- 1\le N\le2\times10 ^ 5
- 1\le A _ i\le N\ (1\le i\le N)
- 1\le B _ i\le N\ (1\le i\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A _ 1 A _ 2 \ldots A _ N B _ 1 B _ 2 \ldots B _ N
Output
Print Yes in one line if it is possible to make A equal to B by performing the operation exactly once, and No otherwise.
Sample Input 1
6 1 4 1 4 2 1 1 4 1 1 4 2
Sample Output 1
Yes
For example, by taking out A _ 6 and inserting it between the 3-rd and 4-th elements of the remaining sequence, A after the operation becomes (1,4,1,1,4,2).
Thus, print Yes.
Sample Input 2
2 1 1 1 2
Sample Output 2
No
No matter what operation is performed on A, it cannot be made equal to B.
Sample Input 3
3 1 2 3 1 2 3
Sample Output 3
Yes
The element taken out may be inserted back at its original position.
Sample Input 4
30 25 11 21 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 18 16 16 20 16 25 11 15 30 20 17 19 17 21 10 13 22 10 22 14 30 25 17 25 11 19 27 27 15 21 18 16 16 20 16
Sample Output 4
Yes