수열과 최대 상승 쿼리

길이가 $N$인 수열 $a\_1, a\_2, ..., a\_N$이 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성해보자.

• 1 k x: $a\_k$를 $x$로 바꾼다.
• 2 l r: 구간 $[l, r]$의 최대 상승 값을 출력한다. 구간 $[l, r]$의 최대 상승 값은 다음과 같이 정의한다. $\max(a\_j-a\_i)\ (l\le i\le j \le 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)$이다.

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