Într-un parc de distracţii s-a introdus un joc nou: tir cu arcul. Participanţii trebuie să ţintească de la o anumită distanţă baloane fixate pe un şir de stâlpi de diferite înălţimi egal distanţaţi unul de altul. Dacă un balon este spart, stâlpul care l-a susţinut se va elimina, iar stâlpii rămaşi se vor repune la distanţe egale. Dacă un arcaş reuşeşte prin acest procedeu ca trei baloane consecutive în şir să fie pe o aceeaşi dreaptă, atunci el va câştiga un premiu consistent.
În exemplul de mai jos din două lovituri se poate obţine premiul:
Patronul a mizat pe faptul că vizitatorii vor fi începători în folosirea arcului sau, chiar dacă ar şti să ţintească bine, nu vor avea o strategie bună pentru eliminarea stâlpilor corespunzători.
Dar când a apărut primul arcaş care era şi profesionist şi deştept, casieria s-a golit. De atunci patronul s-a hotărât serios să pună stâlpii într-o ordine care să nu permită obţinerea premiului.
Cerinţă
Cunoscând numărul n al stâlpilor şi înălţimile lor h1, h2, ..., hn, să se determine, dacă este posibil, o aranjare a lor, astfel încât să fie imposibilă aducerea a trei baloane pe o dreaptă.
Date de intrare
Fişierul arctir.in conţine pe prima linie numărul n al stâlpilor. Următoarea linie conţine n numere naturale separate prin câte un spaţiu, reprezentând şirul înălţimilor stâlpilor h1, h2, ..., hn.
Date de ieşire
Fişierul arctir.out conţine o singură linie pe care se găsesc înălţimile stâlpilor în ordinea din aranjarea determinată conform cerinţelor, separate prin câte un spaţiu, sau numărul -1 dacă nu există o astfel de aranjare.
Restricţii
• 0 < n ≤ 5000
• 0 < hi ≤ 10 000 000, 1≤i≤n
• Diferenţa dintre înălţimea maximă şi înălţimea minimă dintre doi stâlpi nu depăşeşte 30000.
• Baloanele sunt punctiforme.
• Pot exista mai multe soluţii, orice soluţie corectă se acceptă.
Exemple
arctir.in
arctir.out
Explicaţii
6
2 4 4 3 6 3
4 4 2 3 6 3
Oricum am vrea să eliminăm elemente interioare, nu vom obţine trei numere care să corespundă a trei baloane pe o dreaptă.
