relee

Fie date altitudinile a N puncte, situate în linie dreaptă de-a lungul axei Ox, astfel încât ele corespund unor abscise naturale consecutive. Primul punct are abscisa 1. Din acest punct trebuie trimisă o rază laser în ultimul punct (cel de abscisa N). Raza se propagă doar în linie dreaptă și nu poate trece sub punctele date (dar poate trece prin ele). Pentru a "ocoli" punctele având altitudini care împiedică trecerea razei, în anumite puncte se montează relee care schimbă unghiul sub care se propagă raza, cu scopul ca ea să poată trece de vârfurile care se află în drumul ei. Releele se vor monta în oricare dintre punctele date, mai puțin în primul punct, de unde raza poate porni sub orice unghi și în ultimul punct unde raza poate fi recepționată sub orice unghi.

S-a observat că dacă în anumite puncte releul se montează pe un pilon, numărul releelor necesare se poate micșora. Toți pilonii care se vor monta au aceeași înălțime dată H.

Cerință

Determinați numărul minim total de relee (înălțate pe pilon sau nu) pentru ca raza să ajungă din punctul inițial în cel final, precum și punctele în care acestea se vor monta. În cazul în care există mai multe soluții cu același număr minim de relee, se va alege cea cu număr minim de piloni.

Date de intrare

Fișierul relee.in conține pe prima linie numerele naturale N - numărul punctelor și H - înălțimea pilonilor. Pe a doua line se vor găsi, separate prin câte un spațiu, altitudinile $A_i$ ale celor N puncte.

Date de ieșire

Pe prima linie a fișierului relee.out se vor afișa, separate printr-un spațiu, numărul de relee care nu sunt înălțate pe piloni, respectiv numărul de relee înălțate pe piloni. Pe a doua linie se vor afișa abscisele punctelor în care se vor monta releele fără să fie înălțate pe piloni. Pe a treia linie se vor afișa abscisele punctelor în care se vor monta releele înălțate pe piloni.

Restricții

• Pentru 50 de puncte: 1 ≤ N ≤ 200, 1 ≤ H ≤ 500, $1 ≤ A_i ≤ 2 \ 500$, i = 1, 2, ..., N
• Pentru alte 50 de puncte: 1 ≤ N ≤ 5 000, 1 ≤ H ≤ 1 000 000 000, $1 ≤ A_i ≤ 1 \ 000 \ 000 \ 000$, i = 1, 2, ..., N
• Se acordă 50% pentru afișarea numărului de relee și 50% pentru afișarea unei variante de amplasare a releelor.
• Dacă trei vârfuri sunt coliniare, atunci pe cel din mijloc nu trebuie amplasat un releu.

Exemplu

relee.in

9 2
3 2 6 6 4 3 5 3 2

relee.out

1 1
7
4

Se montează 2 relee: 1 înălțat pe pilon și 1 neînălțat. Releu fără pilon se va monta în punctul 7, iar pe pilon în punctul 4. O altă variantă este să punem releul cu pilon în punctul 3. Dacă am pune relee în punctele 3, 4, 7, am putea să nu folosim niciun pilon dar utilizăm 3 relee în loc de 2.

Exemplul corespunde următoarei figuri: