Problem
Implemente una estructura de datos para calcular eficientemente el máximo de elementos de matriz consecutivos.
Entrada
La primera línea contiene un número natural
N (
\(1 <= N <= 100000\)) — el número de números en la matriz. La segunda línea contiene números
N del 1 al 100000 — elementos de matriz. La tercera línea contiene un número natural
K (
\(1 <= K <= 30000\)) &mdash ; el número de solicitudes para calcular el máximo. En las siguientes líneas
K, ingrese dos números cada una — los números de los elementos izquierdo y derecho del segmento de matriz (se supone que los elementos de la matriz están numerados a partir de uno).
Impresión
Para cada consulta, imprime el valor del elemento máximo en el rango especificado de la matriz. Muestra los números en una línea separados por un espacio.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |