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