특별한 숙제 순서 바꾸기

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

요약

1부터 N까지의 순열을 인접한 세 원소를 오름차순 또는 내림차순으로 정렬하는 연산을 반복해서 목표 순열로 바꿀 수 있는지 판별합니다.

문제

Mr Singh은 NLCS Jeju의 선생님이다. 그는 IB 과정 때문에 힘들어하는 12학년 학생들을 위해 수업 계획을 짜고 있다.

Mr Singh은 학생들이 받을 숙제의 순서인 숙제 계획을 짰다. 숙제 계획에는 $N$ 개의 숙제가 있고, 각 숙제에는 1 이상 $N$ 이하의 고유 번호가 붙어 있다.

숙제 계획을 본 학생들은 화가 나서 선생님에게 요구안을 제시하였다.

Mr Singh은 학생들의 요구를 들어주기로 했지만 커리큘럼은 망치고 싶지 않다. 그래서 다음 작업을 몇 번이든 실행해서 원래 숙제 계획을 요구안으로 바꿀 수 있는지 알아보려 한다.

Mr Singh이 이 작업을 몇 번이든 반복해서 원래 숙제 계획을 요구안으로 바꿀 수 있는지 조사하는 프로그램을 작성하시오.

첫 번째 줄에 $N$ 이 주어진다.

두 번째 줄에 원래 숙제 계획이 주어진다. $N$ 개의 서로 다른 정수가 공백으로 구분되어 주어지며, 모든 정수는 1 이상 $N$ 이하이다.

세 번째 줄에 학생들이 제시한 요구안이 두 번째 줄과 같은 형식으로 주어진다.

첫 번째 줄에 Mr Singh이 이 작업을 몇 번이든 실행해서 원래 숙제 계획을 요구안으로 바꿀 수 있으면 POSSIBLE을, 바꿀 수 없으면 IMPOSSIBLE을 출력한다. 대소문자에 유의한다.

$3 \leq N \leq 100\,000$