Olimpiada de informatică - faza pe școală SEB clasa a 8-a - Mirror | orase

Dorel are o casă în punctul $0$. El a vizitat $n$ orașe care sunt în punctele $a_1, a_2, \dots, a_n$. Spunem că un oraș i-a plăcut lui Dorel dacă valoarea punctului în care se află este primă. El vrea să știe în câte moduri poate alege $3$ orașe distincte, care i-au plăcut, pentru care distanța dintre oricare două orașe este mai mică sau egală cu un $x$.

Cerință

Se dau două numere întregi $n$ și $x$, și un șir crescător de $n$ numere întregi, $a_1 \leq a_2 \leq \dots \leq a_n$. Să se afle în câte moduri se pot alege trei numere prime din șir, fie acestea $a_p, a_q, a_r \ (p \lt q \lt r)$, care au următoarea proprietate: Considerăm numerele $a_q - a_p$, $a_r - a_q$, $a_r - a_p$. Dorim ca toate să fie mai mici sau egale cu $x$.

Date de intrare

Pe prima linie a fișierului de intrare orase.in se găsesc două numere întregi, $n$ și $x$. Pe a doua linie se vor găsi cele $n$ numere $a_1, a_2, \dots, a_n$.

Date de ieșire

Pe prima linie a fișierului de ieșire orase.out se va găsi un singur număr întreg, rezultatul.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$
• $0 \leq a_1 \leq a_2 \leq .. \leq a_n \leq 10 ^ 6$
• $1 \leq x \leq 10 ^ 6$
• Pentru $40$ de puncte, $n \leq 100$.
• Pentru alte $30$ de puncte, $n \leq 10 \ 000$.

Exemplu

orase.in

8 5
2 3 4 5 7 8 11 13

orase.out

4

Explicație

Tripletele alese sunt: $(2, 3, 5)$, $(2, 3, 7)$, $(2, 5, 7)$, $(3, 5, 7)$.