Naturālu skaitļu virkni $\{a_i\}$ sauksim par zāģa virkni, ja tās locekļus saista sakarība:

$a_1 < a_2 > a_3 < a_4 > \ldots$

Piemēram, zāģa virknes ir 7, 8, 4, 13, 4 un 7, 13, 4, 8, 4, bet nav – 4, 4, 13, 8, 7 un 13, 4, 8, 4, 7.

Ja zāģa virknē ir vairāk par vienu elementu, tad šādai virknei varam aprēķināt katru divu blakus skaitļu starpību pēc moduļa $|a_{i+1} - a_i|$ un tad atrast mazāko no šīm starpībām.

Piemēram, ja doti skaitļi 1, 2, 4, 4, 7, 7, 9, 11, 12, tad no tiem var izveidot vairākas zāģa virknes ar atšķirīgu mazāko blakus skaitļu starpību pēc moduļa:

• 11-12-7-9-4-7-2-4-1 (mazākā starpība 1)
• 1-4-2-12-4-11-7-9-7 (2)
• 4-7-4-12-1-9-2-11-7 (3)
• 2-7-1-11-4-9-4-12-7 (5)

Šajā piemērā 5 ir lielākā iespējamā mazākās starpības vērtība.

Uzrakstiet datorprogrammu, kas dotus $N$ naturālus skaitļus sakārto zāģa virknē tā, ka mazākā divu blakus skaitļu starpība pēc moduļa ir lielākā iespējamā!

Pirmajā rindā dota naturāla skaitļa $N$ (skaitļu skaits, $2 \leq N \leq 10^5$) vērtība. Otrajā rindā doti $N$ naturāli skaitļi, kas atdalīti ar tukšumzīmēm. Neviens no dotajiem skaitļiem nepārsniedz $10^9$.

Izvaddatu pirmajā rindā jāizvada naturāls skaitlis $S$ – lielākā iespējamā zāģa virknes, kuru iespējams izveidot no dotajiem skaitļiem, divu blakus skaitļu mazākā starpība pēc moduļa.

Otrajā rindā jābūt dotajiem $N$ naturālajiem skaitļiem, kas sakārtoti zāģa virknē tā, ka mazākā divu blakus skaitļu starpība pēc moduļa ir $S$. Ja iespējams izveidot vairākas zāģa virknes ar blakus skaitļu starpību $S$, jāizvada jebkura no tām.

Ja no dotajiem skaitļiem izveidot zāģa virkni nav iespējams, tad izvaddatu pirmajā rindā jāizvada 0 un otrajā – dotie skaitļi patvaļīgā secībā.

Starp katriem diviem blakus skaitļiem izvaddatos jābūt tukšumzīmei.