maximum-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 element in the range "i" to "j" both inclusive.
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
5
5
10

Explanation

Given list is 1-based index as mentioned in problem statement, for the first query "Q 1 8"  we have to find the maximum element from the range 1 to 8 both inclusive, answer is 5 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 element from the index 4 to 6 both inclusive and 10 is the right answer

Source: hackerearth | Difficulty: EASY


Solutions: