Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

OBI4CCBO - Suma Maxima de intervalos

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


ID RESULT TIME
code...



Adicionado por:Edwin Guzman
Fecha:2014-10-29
Tiempo límite:1s
Límite del código fuente:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Lenguajes:C CSHARP C++ 4.3.2 CPP CPP14 JAVA

ocultar comentarios
2014-11-03 19:49:38 Eddy Cael
Si cargaron el mismo dataset de Tarija esta mal... No cumple que 1<=x<y<=N . Me pregunto como lo resolvieron los que ganaron en Tarija.
UPD: Ya modificaron el DataSet... Ahora si esta correcto.. No esta erroneo como el de Tarija. :D


Última edición: 2014-11-06 15:38:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.