수열과 장난

"음 심심한걸? 어디 장난칠 대상이 없나?"

"오 저기 마침 수열이 보이네? 한 번 재밌게 만들어 보자!"

출제자의 레이더에 걸려버린 우리의 친구, 수열 $A$.

출제자의 레이더에 걸린 모든 것은 제 모습을 찾기 힘들다고 전해진다... 이번엔 $A$가 걸려버렸으니...

출제자는 악행으로 유명해서 어떤 장난을 치는지, 어떤 순서로 치는지도 전부 알려져 있다.

출제자는 다음과 같은 3가지 방법으로 장난을 친다.

• 1 $i$: $i$번째에 있는 수를 제거한다. 이 수를 제거하면 $A$의 원소들의 인덱스가 바뀔 수 있다.
• 2 $i$ $r$: 앞에서부터 $i-r$번째부터 $i+r$번째까지의 모든 수에서, 그 구간에 있는 수 중 최솟값을 뺀다.
• 3 $i$ $r$: 앞에서부터 $i-r$번째부터 $i+r$번째까지의 모든 수에, 그 구간에 있는 수 중 최댓값을 더한다.

출제자는 장난을 치면서 궁금증이 생겼다. 다음과 같이 $A$의 범위를 말해주면 우리의 수열은 3번째로 큰 수를 알려줘야 한다.

• 4 $l$ $r$: 앞에서부터 $l$번째부터 $r$번째까지의 범위를 말해준다. 그러면 $A_l$, $A_{l+1}$, ..., $A_r$ 원소 중 3번째로 큰 값을 알려준다. 단, 같은 수는 하나로 세고, 3번째로 큰 수가 존재하지 않으면 -1을 대답한다.

첫 번째 줄에 $A$가 장난을 당하기 전의 길이 $N$ ($5 \le N \le 500\,000$)이 주어진다.

두 번째 줄에 장난을 당하기 전의 수열 $A$가 주어진다. $A$의 원소는 $10^{9}$ 이하의 양의 정수이다.

세 번째 줄에 장난의 횟수와 $A$를 궁금해하는 횟수를 합한 값 $Q$ ($3 \le Q \le 300\,000$)가 주어진다.

네 번째 줄부터 $Q$개의 줄에 장난의 종류와 위치, 또는 출제자가 궁금해하는 $A$의 범위가 한 줄에 하나씩 주어진다.

1번 장난으로 수열의 길이가 0이 되지 않는다. 2번과 3번 장난에서 $r$은 음이 아닌 정수이고, $i-r$은 1 이상이며, $i+r$은 장난을 칠 때의 수열 길이를 넘지 않는다. 3번 장난으로 증가한 수열의 원소는 $2^{63}-1$ 이하이다. 출제자는 적어도 한 번은 궁금해한다.

출제자가 궁금해할 때마다 정답을 한 줄에 하나씩 출력한다.