Máximos em subseções
Problem
Implemente uma estrutura de dados para calcular eficientemente os máximos de elementos consecutivos do array.
Entrada
A primeira linha contém um número natural
N (
\(1 <= N <= 100000\)) — o número de números na matriz. A segunda linha contém
N números de 1 a 100000 — elementos da matriz. A terceira linha contém um número natural
K (
\(1 <= K <= 30000\)) &mdash ; o número de solicitações para calcular o máximo. Nas
K linhas a seguir, insira dois números cada — os números dos elementos esquerdo e direito do segmento do array (presume-se que os elementos do array são numerados a partir de um).
Impressão
Para cada consulta, imprima o valor do elemento máximo no intervalo especificado da matriz. Imprima os números em uma linha separada por um espaço.
Exemplos
| # |
Entrada |
Saída |
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |