Hangyák

Egy seregnyi hangya sétál egy l cm hosszú vízszintes rúdon, mindegyikük állandó 1 cm/s sebességgel. Amikor egy hangya eléri a rúd egyik végét, azonnal leesik róla. Ha két hangya találkozik, megfordulnak, és az ellenkező irányban haladnak tovább. Ismerjük a hangyák eredeti pozícióit a rúdon, de sajnos nem tudjuk, milyen irányban sétálnak. A feladatod, hogy kiszámítsd a legkevesebb és a legtöbb időt, amely ahhoz szükséges, hogy minden hangya leessen a rúdról.

A bemenet specifikációja

A bemenet első sora egy egész számot tartalmaz, amely a tesztesetek számát adja meg. Az egyes tesztesetek két egész számmal kezdődnek: a rúd hosszával (cm-ben) és n-nel, a rúdon lévő hangyák számával. Ezt a két számot n egész szám követi, amelyek az egyes hangyák rúdon elfoglalt pozícióját adják meg a rúd bal végétől mért távolságként véletlenszerű sorrendben. A bemeneten szereplő egész számok egyike sem haladja meg az 1 000 000-t, és fehér karakterekkel vannak egymástól elválasztva.

A kimenet specifikációja

Minden tesztesetre két számot kell a kimenetre írni külön sorban, egyetlen szóközzel elválasztva. Az első szám a legkevesebb, a második pedig a legtöbb időt adja meg (másodpercben), amennyi ahhoz szükséges, hogy minden hangya leessen a rúdról (megfelelően választva meg a haladásuk irányát).

Példa bemenet

1. 2
2. 10 3
3. 2 6 7
4. 214 7
5. 11 12 7 13 176 23 191

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 4 8
2. 38 207

letöltés szöveges állományként