Relee

Fie date altitudinile a N puncte, situate în linie dreapta de-a lungul axei Ox, astfel încât ele corespund unor abscise naturale consecutive. Primul punct are abscisa 1. Din acest punct trebuie trimisa o raza laser în ultimul punct (cel de abscisa N). Raza se propaga doar în linie dreapta. Pentru a "ocoli" punctele având altitudini care împiedica trecerea razei, în anumite puncte se monteaza relee care schimba unghiul sub care se propaga raza, cu scopul ca ea sa poata trece de vârfurile care se afla în drumul ei. Releele se vor monta în oricare dintre punctele date, mai putin în primul punct, de unde raza poate porni sub orice unghi si în ultimul punct unde raza poate fi receptionata sub orice unghi.

S-a observat ca daca în anumite puncte releul se monteaza pe un pilon, numarul releelor necesare se poate micsora. Toti pilonii care se vor monta au aceeasi înaltime data H.

Cerinta

Determinati numarul minim de relee pentru ca raza sa ajunga din punctul initial în cel final, precum si punctele în care acestea se vor monta. În cazul în care exista mai multe solutii cu acelasi numar minim de relee, se va alege cea cu numar minim de piloni.

Date de intrare

Fisier de intrare: RELEE.IN

Linia 1: N H

Linia 2: A1 A2 ... AN

Date de iesireFisier de iesire: RELEE.OUT

Linia 1: NRrelee

Linia 2: NRpiloni

Linia 3: C1 C2 ... CNRrelee

Linia 4: D1 D2 ... DNRpiloni

Restrictii

Exemplu

RELEE.IN


9 2
3 2 6 6 4 3 5 3 2

RELEE.OUT
1
1
7
4


Liniile punctate reprezinta altitudinea punctelor date.
Releu fara pilon se va monta în punctul 7, iar pe pilon în punctul 4.

Timp maxim de executie/test: 2 secunde