Massimi sulle sottosezioni
Problem
Implementa una struttura dati per calcolare in modo efficiente i massimi di elementi consecutivi dell'array.
Inserimento
La prima riga contiene un numero naturale
N (
\(1 <= N <= 100000\)) — il numero di numeri nell'array. La seconda riga contiene
N numeri da 1 a 100000 — elementi dell'array. La terza riga contiene un numero naturale
K (
\(1 <= K <= 30000\)) &mdash ; il numero di richieste per calcolare il massimo. Nelle seguenti
K righe, inserisci due numeri ciascuna — i numeri degli elementi sinistro e destro del segmento dell'array (si presuppone che gli elementi dell'array siano numerati a partire da uno).
Impressum
Per ogni query, stampa il valore dell'elemento massimo nell'intervallo specificato dell'array. Emetti i numeri in una riga separati da uno spazio.
Esempi
| # |
Input |
Uscita |
| 1 |
5
2 2 2 1 5
2
23
25 |
2 5 |