Maximum Sum
Maximum Sum
You are given a sequence of integers a1
, a2
, ..., an
(0 ≤ ai
≤ 108
, 2 ≤ n ≤ 105
). There are two types of operations and they are defined as follows:
Update:
This will be indicated in the input by a 'U' followed by space and then two integers i and x.
U i x, 1 ≤ i ≤ n and 0 ≤ x ≤ 108
This operation sets the value of ai
to x.
Query:
This will be indicated in the input by a 'Q' followed by a single space and then two integers i and j.
Q x y, 1 ≤ x < y ≤ n
You must find i and j such that x ≤ i, j ≤ y and i ≠ j, such that the sum ai
+ aj
is maximized. Print the sum ai
+ aj
.
Input
The first line consists of an integer n representing the length of the sequence. Next line consists of n integers ai
. Next line contains an integer q (q ≤ 105
), representing the number of operations. Next q lines contain the operations.
Output
Print in a separate line the maximum sum mentioned above for each Query.
5 1 2 3 4 5 6 Q 2 4 Q 2 5 U 1 6 Q 1 5 U 1 7 Q 1 5
7 9 11 12