MOG
Spanish
|
English

Matcom Online Grader

II Copa MATCOM ACM-ICPC

Ended

A - Intervalo de Suma Máxima

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Dada una lista de $N$ enteros $\{x_1, x_2, \dotsc, x_N\}$ y un conjunto de $Q$ preguntas definidas como $[a, b]$ usted debe calcular el intervalo de suma máxima que está completamente contenido en $[a, b]$. En otras palabras, dado dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ usted debe buscar el intervalo $[i, j]$ tal que $a \le i \le j \le b$ y maximice $x_{i} + x_{i+1} + \dotsb + x_{j}$.

Input

Línea 1 : Un único entero $N$ $(1 \le N \le200000)$.
Línea 2 : $N$ enteros separados por espacio $x_1, x_2, \dotsc, x_N$ $(|xi| ≤ 10000)$.
Línea 3 : Un único entero $Q$ $(1 \le Q \le200000)$.
Línea 4… Q + 3 : Dos enteros $a$ y $b$ $(1 \le a \le b \le N)$ por línea.

Output

Línea 1…Q : Por cada pregunta imprima el valor del intervalo de suma máxima contenido completamente en $[a, b]$.

Sample test(s)

Input
10 4 -2 -1 5 -1 0 10 -9 8 -3 5 1 1 2 2 1 10 3 5 4 9
Output
4 -2 15 5 14

Hints

Considere el caso en el ejemplo:

Pregunta

Intervalo De Suma Máxima

Suma

1 1

1 1

4

2 2

2 2

-2

1 10

1 7

4+(-2)+(-1)+5+(-1)+0+10 = 15

3 5

4 4

5

4 9

4 7

5+(-1)+0+10=14