Maximum Sum
You are given a sequence of integers a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 10^8, 2 ≤ n ≤ 10^5). 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 ≤ 10^8
This operation sets the value of a[i] 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 a[i] + a[j] is maximized. Print the sum a[i] + a[j].
Input
The first line consists of an integer n representing the length of the sequence. Next line consists of n integers a[i]. Next line contains an integer q (q ≤ 10^5), 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.