Programacion Competitiva Bolivia

Suma Maxima de intervalos

Dejemos la historia de lado y vamos al grano! Te daremos una secuencia de numeros A[1], A[2], ... , A[N] (0≤A[i]≤10^8, 2≤N≤10^5), donde existiran 2 tipos de operaciones

Update: Esta operacion es indicada con la letra U seguido por 2 enteros i, c donde (1≤i≤N y 0≤C≤10^8) U i c -> Esto indica que el valor A[i] sera modificado por el valor c.

Query: Esta operacion es indicada por la letra Q seguido por 2 enteros x, y (1≤x<y≤N) Q x y -> Donde debes encontrar un i, j talque x≤i, j≤y, i!=j talque la suma de A[i] + A[j] es maxima

Input

La primera linea de la entrada consiste en un entero N representado la longitud de la secuencia. La siguiente linea estara compuestas de N enteros A[i], A continuacion un entero D(D≤10^5), representando el numero de operaciones que se deberan realizar. D lineas vienen a continuacion indicando las operaciones senaladas anteriormente. (Como puedes notar solo hay un caso de prueba y es muy largo :) )

Output

Imprimir la suma maxima por cada Q realizada en la entrada de datos.

Example

Input:
5
1 2 3 4 5
6
Q 2 4
Q 2 5
U 1 6
Q 1 5
U 1 7
Q 1 5

Output:
7
9
11
12