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
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
