문제

수열과 최대 상승 쿼리 (Easy)와 (Hard)는 입력 조건을 제외하고 차이가 없다.

길이가 $N$인 수열 $a_1, a_2, ..., a_N$이 주어졌을 때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

• 1 k x: $a_k$를 $x$로 바꾼다.

• 2 l r: 구간 $[l, r]$의 최대 상승 값을 출력한다. 구간 $[l, r]$의 최대 상승 값은 다음과 같이 정의한다.

입력

첫째 줄에 수열의 길이 $N(1 \le N \le 100\ 000)$가 주어진다.

두 번째 줄에 수열의 원소 $a_1, a_2, ..., a_N$이 주어진다. 수열의 $i$번째 원소는 정수 $a_i(-10^9 \le a_i \le 10^9)$이다.

세 번째 줄에 쿼리의 개수 $Q(1 \le Q \le 100\ 000)$이 주어진다.

네 번째 줄부터 $Q$개의 줄에 쿼리가 주어진다.

쿼리는 $1\ \ k\ \ x(1 \le k \le N, -10^9 \le x \le 10^9)$ 혹은 $2\ \ l \ \ r(1\le l \le r\le N)$이다.

두 번째 쿼리는 적어도 하나 주어진다.

출력

두 번째 쿼리의 수행 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
4 2 3 1 5
4
2 1 4
2 2 5
1 3 2
2 2 4

예제 출력 1

1
4
0

예제 입력 2

3
3 1 2
4
2 1 3
2 1 1
1 3 4
2 1 3

예제 출력 2

1
0
3