orase

Time limit: 0.05s Memory limit: 64MB Input: orase.in Output: orase.out

Dorel are o casă în punctul 00. El a vizitat nn orașe care sunt în punctele a1,a2,,ana_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 33 orașe distincte, care i-au plăcut, pentru care distanța dintre oricare două orașe este mai mică sau egală cu un xx.

Cerință

Se dau două numere întregi nn și xx, și un șir crescător de nn numere întregi, a1a2ana_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 ap,aq,ar (p<q<r)a_p, a_q, a_r \ (p \lt q \lt r), care au următoarea proprietate: Considerăm numerele aqapa_q - a_p, araqa_r - a_q, arapa_r - a_p. Dorim ca toate să fie mai mici sau egale cu xx.

Date de intrare

Pe prima linie a fișierului de intrare orase.in se găsesc două numere întregi, nn și xx. Pe a doua linie se vor găsi cele nn numere a1,a2,,ana_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

  • 1n100 0001 \leq n \leq 100 \ 000
  • 0a1a2..an1060 \leq a_1 \leq a_2 \leq .. \leq a_n \leq 10 ^ 6
  • 1x1061 \leq x \leq 10 ^ 6
  • Pentru 4040 de puncte, n100n \leq 100.
  • Pentru alte 3030 de puncte, n10 000n \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, 5), (2,3,7)(2, 3, 7), (2,5,7)(2, 5, 7), (3,5,7)(3, 5, 7).

Log in or sign up to be able to send submissions!