maximu-sum

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

Source: hackerearth | Difficulty: MEDIUM


Solutions: