Sequence and Maximum Rise Queries

Given a sequence $a\_1, a\_2, ..., a\_N$ of length $N$, write a program that processes the following queries.

• 1 k x: Change $a\_k$ to $x$.
• 2 l r: Print the maximum rise of the interval $[l, r]$. The maximum rise of $[l, r]$ is defined as $\max(a\_j-a\_i)\ (l\le i\le j \le r)$

The first line contains the length $N$ ($1 \le N \le 100\ 000$) of the sequence.

The second line contains the elements $a\_1, a\_2, ..., a\_N$ of the sequence. The $i$-th element $a\_i$ is an integer ($-10^9 \le a\_i \le 10^9$).

The third line contains the number of queries $Q$ ($1 \le Q \le 100\ 000$).

Each of the next $Q$ lines contains a query. A query consists of three integers, either $1\ \ k\ \ x$ ($1 \le k \le N$, $-10^9 \le x \le 10^9$) or $2\ \ l\ \ r$ ($1 \le l \le r \le N$).

At least one query of type 2 is given.