Se consideră şirul de numere p(1), p(2), p(3), ..., p(n), acestea fiind numere naturale distincte din mulţimea {1,2,..., n}. Luăm în considerare numai subşirurile x(1), x(2), ..., x(k) ale acestui şir având următoarele proprietăţi:

• x(1) = p(1) şi x(k) = p(n)
• pentru orice doi termeni alăturaţi x(j) şi x(j+1) ai subşirului, x(j) şi x(j+1) au reprezentările în baza 2 care diferă prin exact un bit. De exemplu, 5 şi 7 îndeplinesc acestă condiţie, deoarece 5 = 101 (în baza 2), 7 = 111 (în baza 2) şi cele două reprezentări diferă doar prin al doilea bit. Dar 3 şi 5 nu o îndeplinesc, pentru că 3 = 011 (în baza 2), 5 = 101 (în baza 2), deci diferă prin doi biţi.

Notând cu |q| modulul numărului q, pentru un subşir construit ca mai sus, valoarea maximă dintre |x(1) - x(2)|, |x(2) - x(3)|, ..., |x(k-1) - x(k)| o numim reziduu.

Cerinţă

Scrieţi un program care să determine subşirul pentru care reziduul este minimum posibil. Dacă sunt mai multe astfel de subşiruri, aflaţi-l pe cel minim lexicografic.

Date de intrare

Fişierul de intrare reziduu.in conţine pe prima linie numărul natural n. Pe linia a doua se găsesc n numerele naturale p(1), p(2), p(3), ..., p(n), separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire reziduu.out va conţine pe prima linie un număr natural reprezentând reziduul minim al subşirului, iar pe linia a doua sunt scrise, separate prin câte un spaţiu, elementele subşirului. Dacă problema nu are nicio soluţie, veţi tipări în fişier pe prima linie un singur 0.

Restricţii

• 1 <= n <= 1 000 000
• Un subşir se obţine dintr-un şir prin eliminarea a zero, unul sau mai multe elemente din şir.

Exemplu

reziduu.in	reziduu.out
7 6 4 2 1 7 5 3	4 6 2 3

prof. Dan Pracsiu

Grupul Şcolar „Ştefan Procopiu” Vaslui

dpracsiu@yahoo.com