Distincte

distincte

== include(page="template/taskheader" task_id="distincte") ==

Zaharel are un vector de $N$ elemente cu valori numere naturale intre $1$ si $K$. El isi pune $M$ intrebari de forma: care este suma elementelor distincte aflate intre pozitiile $i$ si $j$ din vector?

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $distincte.in$ contine pe prima linie numerele $N, K, M$ separate prin spatii. Urmatoarele $N$ linii vor contine elemente din vector. Urmatoarele $M$ linii vor descrie intrebarile: cate doua numere $i, j (1 ≤ i ≤ j ≤ N)$ separate prin spatii pe fiecare linie.

...

h2. Date de iesire

In fisierul de iesire $distincte.out$ se vor scrie $M$ numere, al $i$-lea numar reprezentand raspunsul pentru a $i$-a intrebare. Rezultatul se va afisa modulo $666013$.

...

h2. Restrictii

* $1 ≤ N, M ≤ 100.000$
* $1 ≤ K ≤ N$
* Elementele din vector sunt numerotate de la $1$ la $N$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. distincte.in |_. distincte.out |

| 6 3 2
1
2
2
1
3
1
2 5
1 4
| 6
3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Elementele din vector intre pozitiile $2$ si $5$ sunt $2 2 1 3$ iar suma celor distincte este $2+1+3 = 6$.
Elementele din vector intre pozitiile $1$ si $4$ sunt $1 2 2 1$ iar suma celor distincte este $1+2 = 3$.

...

== include(page="template/taskfooter" task_id="distincte") ==

1755