subsiruri3

Subsiruri 3

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

Poveste şi cerinţă...

Aurel are un sir de $N$ numere intregi $x{~1~}, x{~2~}, …, x{~N~}$. El vrea sa afle in cate moduri poate alege un subsir $x{~i{~1~}~}, x{~i{~2~}~}, …, x{~i{~T~}~}$ cu proprietatea ca $0 ≤ x{~i{~j~}~} - x{~i{~j-1~}~} ≤ K$ pentru $j = 2 … T$. Ajutati-l pe Aurel sa raspunda la aceasta intrebare.

h2. Date de intrare

Fişierul de intrare $subsiruri3.in$ ...

Fişierul de intrare $subsiruri3.in$ va contine pe prima linie $T$, numarul de teste. Fiecare test va avea pe prima sa line doua numere naturale, $N$ si $K$, avand semnificatia din enunt. Urmatoarea linie contine $N$ numere intregi, separate printr-un spatiu, reprezentand sirul lui Aurel.

h2. Date de ieşire

În fişierul de ieşire $subsiruri3.out$ ...

În fişierul de ieşire $subsiruri3.out$ se vor afisa $T$ linii, pe linia $i$ aflandu-se numarul de subsiruri cu proprietatea din enunt pentru testul $i$, modulo **666013**.

h2. Restricţii

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

* $1 ≤ T ≤ 5$
* $1 ≤ N ≤ 10^6^$
* $0 ≤ K ≤ 10^9^$
* $0 ≤ x{~i~} ≤ 10^9^ pentru i = 1 … N$
* $Se numeste subsir al sirului X = (x{~1~}, x{~2~}, …, x{~N~}), un sir Y = (x{~i{~1~}~}, x{~i{~2~}~}, …, x{~i{~T~}~}) cu proprietatea 1 &le; i{~1~} < i{~2~} < … < i{~T~} &le; N$

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

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

| 1
  4 2
  6 2 8 9
| 7

|
h3. Explicaţie

...

Cele 7 subsiruri sunt: {6}, {2}, {8}, {9}, {6, 8}, {6, 8, 9}, {8, 9}.

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

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

9835