Maximum Sum#2911
You are given a sequence of integers a_1, a_2, \ldots, a_n (0 \leq a_i \leq 10^8, 2 \leq n \leq 10^5). There are two types of operations, defined as follows:
_Update:_
This is indicated in the input by a **U** followed by a space and then two integers and .
**U** , 1 \leq i \leq n, 0 \leq x \leq 10^8
This operation sets the value of a_i to .
_Query:_
This is indicated in the input by a **Q** followed by a space and then two integers and .
**Q** , 1 \leq x < y \leq n
You must find and such that x \leq i, j \leq y and i \neq j, so that the sum a_i + a_j is maximized. Print the sum a_i + a_j.
The first line consists of an integer representing the length of the sequence.
The next line consists of integers a_1, a_2, \ldots, a_n.
The next line contains an integer (q \leq 10^5), representing the number of operations.
The next lines contain the operations.
Print, on a separate line, the maximum sum mentioned above for each **Q** operation.
Παράδειγμα 1