31481번 - 수열과 장난

문제

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

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

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

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

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

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

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

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

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

$A$는 장난을 당하는 중이라서 자신의 수열을 살펴볼 수 없다. 따라서 우리가 대신 알려주도록 하자!

입력

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

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

세 번째 줄엔 장난을 당하는 횟수와 $A$가 궁금할 때의 횟수 합인 $Q(3 \le Q \le 300,000円)$가 주어진다.

네 번째 줄부터 $Q$개의 줄엔 장난의 종류와 그 위치 또는 $A$가 궁금한 $A$ 수열의 범위가 각 줄에 하나씩 주어진다.

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

출력

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

제한

힌트