În scopul alimentării cu energie electrică a unui nou cartier de vile, au fost amplasaţi n stâlpi, pentru susţinerea cablurilor care transportă energia electrică. Toţi cei n stâlpi, sunt poziţionaţi de-a lungul unei semidrepte, cu originea în staţia de alimentare. Coordonatele stâlpilor în raport cu staţia de alimentare, sunt numere naturale distincte. O comisie însărcinată cu verificarea lucrărilor a constatat că nu s-au respectat întocmai specificaţiile tehnice privitoare la distanţa minimă, respectiv maximă dintre oricare doi stâlpi consecutivi. Prin urmare, firma care a efectuat lucrările, trebuie să mute o parte dintre cei n stâlpi, astfel încât, distanţa minimă dintre oricare doi stâlpi consecutivi să fie de cel puţin K metri, iar distanţa maximă să nu depăşească P metri. A muta un stâlp, înseamnă, a-l scoate din pământ, a-l deplasa pe o anumită distanţă, pe linia care uneşte poziţiile tuturor stâlpilor, şi a-l fixa în pământ, într-o poziţie finală, a cărei distanţă faţă de staţia de alimentare este exprimată în metri, şi este un număr întreg, pozitiv. Prin urmare, mutarea unui stâlp este o operaţie costisitoare. De aceea, firma are interesul să mute un număr cât mai mic de stâlpi. Să considerăm un sistem unidimensional de coordonate Ox, cu staţia de alimentare plasată în origine. Atunci atât coordonatele iniţiale, cât şi cele finale ale tuturor stâlpilor, vor fi valori întregi, nenegative. Într-o poziţie oarecare, inclusiv în staţia de alimentare, se poate amplasa doar un singur stâlp.
Cerinţă
Determinaţi numărul minim de stâlpi care trebuie mutaţi din poziţiile actuale, pentru a se obţine un amplasament final care respectă specificaţiile tehnice.
Date de intrare
Fişierul stalpi.in conţine pe prima linie numerele naturale n, K, P separate prin câte un singur spaţiu. Pe linia a doua este scrisă o secvenţă strict crescătoare de n numere naturale x1, x2, ... xn despărţite prin câte un spaţiu. Al i-lea număr din secvenţă reprezintă distanţa exprimată în metri, la care se găseşte stâlpul i în raport cu staţia de alimentare.
Date de ieşire
Fişierul stalpi.out va conţine pe prima linie numărul natural S, reprezentând numărul minim de stâlpi care trebuie să fie mutaţi.
Restricţii
1 ≤ n ≤ 2500
0 ≤ x1 < x2 < ... < xn ≤ 2500
1 ≤ K ≤ 10
K ≤ P ≤ 50
Exemple
stalpi.in
stalpi.out
Explicaţii
3 2 4
2 3 4
1
Se mută stâlpul 2, dincolo de stâlpul 3, la o distanţă de cel puţin 2 metri faţă de acesta.
5 2 4
1 6 7 9 14
2
O variantă posibilă: se mută stâlpul 3 de coordonată 7, între stâlpii 1 şi 2, la distanţa 2 sau 3 de stalpul 1, iar apoi se mută stâlpul 5 la distanţa 2, 3, sau 4 metri de stalpul 4.