같은 배열

시간 제한1초메모리 제한1024 MB

요약
길이 N인 배열 A에서 이전 위치의 원소를 골라 뒤에 N번 덧붙여 길이 2N인 B를 정확히 만들 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
그리디, 큐, 투 포인터, 배열
정답자
아직 제출이 없습니다

문제

길이가 NN인 배열 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots , A\_N과, 길이가 2N2N인 배열 B_1,B_2,⋯ ,B_2NB\_1, B\_2, \cdots ,B\_{2N}이 주어진다.

당신은 아래의 연산을 배열 AA에 NN번 수행해야 한다.

  • 현재 배열 AA의 길이를 MM이라고 할 때, 1≤i≤M1\leq i\leq M를 만족하는 ii를 고른다.
  • 이후 A_iA\_i를 배열 AA의 뒤에 삽입한다. 즉, 배열 AA는 \[A_1,A_2,⋯ ,A_M,A_i]\[A\_1, A\_2, \cdots , A\_M, A\_i ]가 된다.

배열 AA에 연산을 적절하게 NN번 수행했을 때, BB와 동일하게 만들 수 있는지 판정해 보자.

입력

첫째 줄에 배열 AA의 초기 길이를 의미하는 정수 NN이 주어진다. (1≤N≤200,000)(1\leq N\leq 200\\, 000)

둘째 줄에 정수 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots , A\_N이 공백으로 구분되어 주어진다. (1≤A_i≤N)(1\leq A\_i\leq N)

셋째 줄에 정수 B_1,B_2,⋯ ,B_2NB\_1, B\_2, \cdots ,B\_{2N}이 공백으로 구분되어 주어진다. (1≤B_i≤N)(1\leq B\_i\leq N)

출력

배열 AA에 연산을 적절하게 NN번 수행했을 때, BB와 동일하게 만들 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

예제3

  1. 예제 1

    입력
    2
    1 2
    1 2 2 1
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    3
    1 2 1
    1 2 1 2 3 1
    
    예상 출력
    NO
    
  3. 예제 3

    입력
    3
    1 3 2
    1 3 3 3 1 2
    
    예상 출력
    NO