You are given a list of elements of size N ( index starts from 1), each element is "a[k]" , k ranges from 1 to N. You have to perform C number of operations on them . An operation is either Update(U) or Query(Q). Update operations have syntax "U i j" , it means the " ith" element a[i] of the list has to be replaced with the value "j" . Query operations have syntax "Q i j" , it means you have to find out the maximum sum of the pair of elements in the range "i" to "j" (both inclusive). i.e maximum sum of pair a[k] and a[l], where i ≤ k < j and i < l ≤ J.

You have to print all the outputs of the queries "Q i j" in each line.

Input Format:
First line consist of N, the size of the number of elements. Second line consists of N elements separated by a space.
Next line consists of the number of queries C to be performed.
Next C lines consists of queries of the form: "U i j" or "Q i j".

Output Format:
Output for all the queries of the form "Q i j" separated by a line.

Constraints:
Elements of list can be fitted in a 4 byte integer : a[i] ≥ 0

1 ≤ N ≤ 1000000

1 ≤ C ≤ 1000000

1 ≤ i < j ≤N

SAMPLE INPUT
10
4 1 0 4 5 5 0 2 2 6
5
Q 1 8
Q 3 9
U 6 10
U 1 6
Q 4 6

SAMPLE OUTPUT
10
10
15

Explanation

Given list is 1-based index as mentioned in problem statement, for the first query "Q 1 8" we have to find maximum sum of the pair of elements 1 to 8(both inclusive) , answer is 10 for the as it can be seen in the list.

3rd query "U 6 10" modifies the 6th element to 10.
5th query "Q 4 6" ,finds the maximum sum of the pair of element from the index 4 to 6 both inclusive and 15 is the right answer

见题面

见题面