che si trovano sul segmento dal
liesimo al
riesimo elemento".< / div>
Una sottosequenza della sequenza a1 , ..., an< /sub> è una sequenza che può essere ottenuta rimuovendo diversi elementi ai (l'ordine relativo dei restanti
Gli elementi
non possono essere modificati). Quindi, ad esempio, la sequenza (2, 4) è una sottosequenza della sequenza (1, 2, 3, 4, 5) (puoi eliminare gli elementi 1, 3 e 5 ), e la sequenza ( 5, 1) non lo è.< br />
Input
La prima riga contiene un numero intero
n (1 <= n <= 3000 ) è il numero di elementi nella sequenza. La seconda riga contiene
n< /code> I numeri separati da spazi sono gli elementi della sequenza. Tutti gli elementi non superano 109 in valore assoluto. La terza riga contiene un singolo numero intero q< /code> (1 < ;= q <= 105) - numero di richieste. Le seguenti righe q descrivono le query. Descrizione della i -esima query - due numeri li e rj (1 <= li <= ri <= n) , separati da spazi.
Emetti dati
Produci q numeri - risposte alle domande. I numeri dovrebbero essere emessi uno per riga nello stesso ordine in cui le query sono descritte nell'input.
Esempi
| # |
Input |
Uscita |
| 1 |
6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25 |
2
1
1
2
2
2 |