Sequence and Queries 24

A sequence $A_1, A_2, \ldots, A_N$ of length $N$ is given. Write a program that performs the following queries.

• 1 i v: change $A_i$ to $v$. ($1 \le i \le N$, $1 \le v \le 10^9$)
• 2 l r: among all $A_i + A_j$ with $l \le i < j \le r$, print the maximum value. ($1 \le l < r \le N$)

Indices of the sequence start at 1.

The first line gives the size of the sequence $N$. ($2 \le N \le 100{,}000$)

The second line gives $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

The third line gives the number of queries $M$. ($2 \le M \le 100{,}000$)

Each of the next $M$ lines gives one query.

For each type 2 query, print the answer on its own line in order.