Module: TABELLA SPARSA

Problem

Ti viene assegnato un array A [1…N]. È necessario eseguire M calcolo dell'elemento minimo sul segmento da L a R.

Inserimento
La prima riga contiene il numero N (\(1 <= N <= 100000\)) – dimensione dell'array. La seconda riga contiene N numeri – elementi dell'array. La terza riga contiene il numero M (\(1 <= M <= 100000\)) – numero minimo di richieste. Le successive righe M contengono coppie di numeri L e R (\(L <= R < = N\)) che descrive i segmenti.

Impressum
Per ogni interrogazione stampa il valore del minimo sul segmento separato da uno spazio.

 

Esempi

#	Input	Uscita
1	5 3 1 8 7 9 2 1 3 3 5	1 7