25639번 - 수열과 최대 상승 쿼리

문제

길이가 $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)$이다.

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

출력

제한

힌트