Cerința
Se dă un șir de N
numere întregi. Să se afle numărul de subsecvențe ale șirului pentru care diferența dintre elementul lor de valoare maximă și cel de valoare minimă este mai mică sau egală decât un număr întreg T
dat.
Date de intrare
Programul citește de la tastatură numerele N
și T
, iar apoi N
numere întregi, separate prin spații.
Date de ieșire
Programul va afișa pe ecran numărul de subsecvențe ale șirului dat care respectă condiția din enunț.
Restricții și precizări
1 ≤ N ≤ 1.000.000
0 ≤ T ≤ 2.000.000.000
- cele
N
numere citite vor fi din intervalul[-1.000.000.000, 1.000.000.000]
- se numește subsecvență a unui șir o succesiune de elemente consecutive din acesta, considerate în ordinea în care apar în șir
- pentru teste în valoare de
30
de puncteN ≤ 10.000
- pentru teste în valoare de
70
de puncteN ≤ 600.000
Exemplu:
Intrare
5 2 1 7 2 3 4
Ieșire
8
Explicație
Cele 8
subsecvențe care respectă condiția din enunț sunt toate cele 5
care conțin un singur element(diferența dintre elementul maxim și cel minim fiind astfel 0
), respectiv cele delimitate de perechile de indecși [3, 4], [3, 5], [4, 5]
(șirul se consideră a fi indexat de la 1
).