곤돌라 수열 확인

마오공 곤돌라는 타이페이의 명소 중 하나이다. 곤돌라는 원형 레일 위를 한 방향으로만 돈다. 정류장은 하나이고, 처음에는 번호 $1$부터 $n$까지인 $n$대가 순서대로 놓여 있다. $i$번이 정류장을 지나면 곧바로 $i+1$번이 지난다 ($n$번 다음은 $1$번).

곤돌라는 고장날 수 있다. 여분은 $n+1, n+2, \ldots$ 순으로 번호가 붙고, 고장난 자리에는 아직 쓰이지 않은 가장 작은 여분 번호가 들어간다. 예를 들어 $n=5$에서 $1$번이 고장나면 $6$번으로 바뀐다.

정류장에서 연속으로 지나가는 $n$대의 번호를 순서대로 적으면 곤돌라 수열이 된다. 기록을 시작하기 전에 이미 여러 번 고장과 교체가 있었을 수 있지만, 기록하는 동안에는 고장이 없다.

같은 배치라도 시작 시점에 따라 수열이 달라질 수 있다. 고장이 없을 때 $(2,3,4,5,1)$과 $(4,5,1,2,3)$은 가능하지만 $(4,3,2,5,1)$은 불가능하다.

$1$번만 고장난 뒤에는 $(4,5,6,2,3)$이 가능하다. 이후 $4$번이 고장나 $7$번으로 바뀌면 $(6,2,3,7,5)$가 가능하다. $7$번이 다시 고장나 $8$번이 들어오면 $(3,8,5,6,2)$도 가능하다.

고장난 순서를 적으면 교체 수열이 된다. 위 예에서는 $(1,4,7)$이다.

입력 수열이 어떤 교체 이력 뒤에도 나올 수 있는 곤돌라 수열인지 판별하라.

첫째 줄에 $n$이 주어진다.

둘째 줄에 $n$개의 정수가 주어진다.

가능하면 $1$, 불가능하면 $0$을 한 줄에 출력한다.

원형 레일에서 각 번호의 바로 다음 번호를 유지하면서, 수열에 없는 원래 번호 $1..n$을 순서대로 여분 번호로 치환한다. 치환으로 생긴 여분 번호도 수열에 없으면 더 큰 여분으로 이어서 바꾼다. 마지막에 입력의 인접한 두 원소가 항상 successor 관계인지 확인한다.