원형 게임

$N$ 명의 사람이 원형으로 앉아 게임을 한다. 사람들은 시계 방향 순서대로 $1$번부터 $N$번까지 번호가 붙어 있다.

첫 번째 라운드에는 모든 사람이 게임에 참가하지만 다음 $M$번의 추가 라운드 동안 다음 $3$가지 쿼리 중 하나로 참여하는 사람의 인원이 변한다.

1. 구간에 속한 사람은 다음 라운드에 모두 참여하지 않는다.
2. 구간에 속한 사람은 다음 라운드에 모두 참여한다.
3. 구간에 속한 사람이 이전 라운드에 참여했다면 다음 라운드에 참여하지 않고, 참여하지 않았다면 다음 라운드에 참여한다.

구간에 속하지 않은 사람은 이전 라운드에 참여했다면 다음 라운드에 참여하고, 참여하지 않았다면 다음 라운드에 참여하지 않는다.

인접한 두 사람의 실력 차가 작을수록 더 즐겁게 게임을 즐길 수 있으므로 라운드마다 인접한 두 사람의 실력 차 중 최댓값을 구해 게임의 재미를 구하려고 한다.

한 라운드에 참여하는 사람이 $1$명 이하라면 실력 차이가 발생할 수 없으므로 실력 차는 $0$이다.

첫째 줄에 사람의 수 $N$과 추가 라운드의 수 $M$이 주어진다. ($2 \leq N \leq 200\\,000$, $1 \leq M \leq 200\\,000$)

둘째 줄에 $N$개의 정수 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다. 이는 $i$번 사람의 실력이 $A\_i$라는 것을 의미한다. ($1 \leq A\_i \leq 10^9$)

셋째 줄부터 $M$개의 줄 중 $i$ 번째 줄에는 쿼리의 번호 $x\_i$, 구간을 의미하는 $l\_i$와 $r\_i$가 공백으로 구분되어 주어진다. ($1 \leq x\_i \leq 3$, $1 \leq l\_i, r\_i \leq N$)

$l\_i \leq r\_i$ 인 경우, $l\_i \leq j \leq r\_i$를 만족하는 $j$번 사람이 구간에 포함된다는 것을 의미하고, $l\_i > r\_i$인 경우, $1 \leq j \leq r\_i$ 혹은 $l\_i \leq j \leq N$을 만족하는 $j$번 사람이 구간에 포함된다는 것을 의미한다.

입력으로 주어지는 모든 수는 정수이다.

첫째 줄에 모든 사람이 참여했을 때의 인접한 두 사람의 실력 차 중 최댓값을 출력한다.

다음 $M$개의 줄에 라운드마다 인접한 두 사람의 실력 차 중 최댓값을 출력한다.