Se consideră un șir de N
numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N]
. În legătură cu acest șir de numere ne interesează perechile de poziții (i,j)
cu 1≤i<j≤N
și a[i]≠a[j]
sau ne interesează suma elementelor anumitor secvențe.
Cerința
Se cere să se scrie un program care să citească un număr C
reprezentând tipul cerinței, un șir de N
numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N]
și T
perechi de numere naturale (p[k],q[k])
cu 1≤p[k]<q[k]≤N
și 1≤k≤T
și apoi:
(1) Dacă C=1
, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q)
suma a[p]+a[p+1]+...+a[q]
.
(2) Dacă C=2
, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q)
numărul de perechi (i,j)
care respectă simultan condițiile p≤i<j≤q
și a[i]≠a[j]
.
Date de intrare
Fișierul de intrare pp.in
conține pe prima linie numărul natural C
. Pe al doilea rând se află numărul N
. Pe al treilea rând sunt scrise N
numere naturale ordonate crescător și separate prin câte un spațiu. Pe al patrulea rând este scris numărul natural T
, iar pe fiecare dintre următoarele T
rânduri câte două numere naturale separate prin câte un spațiu.
Date de ieșire
Dacă C=1
, atunci fișierul de ieșire pp.out
va conține pe fiecare dintre primele T
linii câte un număr natural. Al k
-lea număr va reprezenta suma elementelor cuprinse între pozițiile p[k]
și q[k]
inclusiv.
Dacă C=2
, atunci fișierul de ieșire pp.out
va conține pe fiecare dintre primele T
linii câte un număr natural. Al k
-lea număr va reprezenta numărul cerut de perechi de indici cuprinși între poziţiile p[k]
şi q[k]
inclusiv.
Restricții și precizări
1 ≤ p[i] < q[i] ≤ N ≤ 100 000
1 ≤ a[1] ≤ a[2] ≤ ... ≤ a[N] ≤ 100 000
1 ≤ T ≤ 1000
Exemplul 1
pp.in
1 5 1 2 3 3 3 2 1 4 2 5
pp.out
9 11
Explicație
Suntem în cazul C=1
. Prima pereche (p,q)
este (1,4)
. Suma valorilor din secvență este 1+2+3+3=9
. A doua pereche (p,q)
este (2,5)
. Suma valorilor din secvență este 2+3+3+3=11
.
Exemplul 2
pp.in
2 5 1 2 3 3 3 2 1 4 2 5
pp.out
5 3
Explicație
Suntem în cazul C=2
. Prima pereche (p,q)
este (1,4)
. Perechile de poziții care conțin numere diferite între ele sunt (1,2)
, (1,3)
, (1,4)
, (2,3)
, (2,4)
. Deci sunt 5
perechi.
A doua pereche (p,q)
este (2,5)
. Perechile de poziții care conțin numere diferite sunt (2,3)
, (2,4)
, (2,5)
. Deci sunt 3
perechi.