pp

Se consideră un şir de N numere naturale nenule ordonate crescător $a_1 \leq a_2 \leq \dots \leq a_N$. În legătură cu acest şir de numere ne interesează perechile de poziţii ($i, j$) cu $1 \leq i < j \leq N$ şi $a_i \neq a_j$ sau ne interesează suma elementelor anumitor secvențe.

Cerinţă

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 \leq a_2 \leq \dots \leq a_N$ şi $T$ perechi de numere naturale $(p_k, q_k)$ cu $1 \leq p_k < q_k \leq N$ şi $1 \leq k \leq T$ şi apoi:

• Dacă $C = 1$, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale $(p, q)$ suma $a_p$ + $a_{p+1}$ + $\dots$ + $a_q$.
• 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 \leq i < j \leq q$ şi $a_i \neq a_j$.

Date de intrare

Fişierul de intrare pp.in conţine pe primul rând 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 \leq p_i < q_i \leq N \leq 100 \ 000$
• $1 \leq a_1 \leq a_2 \leq \dots \leq a_N \leq 100 \ 000$
• $1 \leq T \leq 1 \ 000$

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.