Un altre de sumes X95620

Donat un vector d’enters diferents (no necessariament ordenat) seguit d’una seqüència de parells d’enters, feu un programa que per cada parell d’elements de la seqüència, calculi la suma dels elements del vector entre aquests dos elements (si el vector estigués ordenat) o doni un missatge d’error si un dels elements del parell (o els dos) no es troba al vector.

És a dir, donat el parell (a,b), el programa calcula ∑_{0≤i<n, a≤vi≤b} v_i (en cas que tant a com b es trobin al vector v).

Per exemple, donat el vector:

10  3  4  7 -1 23 11  6

pel parell (3,10) el vostre programa hauria de calcular 30 que és la suma dels elements del vector entre el 3 i el 10 (ambdos inclosos). En canvi pels parells (−1,2), (8,11) i (9,24) el programa ha de donar un missatge d’error perquè tots aquests parells contenen almenys un element que no és al vector.

Entrada

L’entrada ve donada per la mida n > 1 del vector seguida dels n elements enters del vector (tots diferents) seguits d’una seqüència de parells d’enters.

Sortida

Per cada parell d’enters de la seqüència d’entrada s’ha d’escriure la suma dels elements del vector amb valors entre els elements del parell (ambdós inclosos) si els dos elements del parell es troben al vector, o bé la paraula error si almenys un dels elements del parell no es troba al vector.

Observació

Cal suposar que el nombre de parells serà molt gran i que el seu tractament ha de ser eficient. El càlcul per a cada parell hauria de fer-se en temps logarítmic. Es recomana fer un preprocés del vector, creant algun vector auxiliar i usant algorismes fonamentals.