Maximums sur les sous-sections
Problem
Implémentez une structure de données pour calculer efficacement les maxima d'éléments de tableau consécutifs.
Entrée
La première ligne contient un nombre naturel
N (
\(1 <= N <= 100000\)) — le nombre de nombres dans le tableau. La deuxième ligne contient
N nombres de 1 à 100000 — éléments du tableau. La troisième ligne contient un nombre naturel
K (
\(1 <= K <= 30000\)) &mdash ; le nombre de requêtes pour calculer le maximum. Dans les lignes
K suivantes, saisissez deux nombres chacune — les numéros des éléments gauche et droit du segment de tableau (on suppose que les éléments du tableau sont numérotés à partir de un).
Mentions légales
Pour chaque requête, imprimez la valeur de l'élément maximum dans la plage spécifiée du tableau. Affichez les nombres sur une ligne séparés par un espace.
Exemples
| # |
Entrée |
Sortie |
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |