AlgoLiga 2018

Dekret

Królowa Bajtolandii, chcąc przypodobać się wiernym poddanym, wydała dekret. Dekret orzeka, że w czasie wakacyjnych weekendów bramki na autostradach całego królestwa mają być otwarte, ale tylko wtedy, gdy będą tworzyły się korki. Poddani cieszą się i radują w przeciwieństwie do zarządców autostrad, którzy dekret ten muszą wprowadzić w życie, a pojęcie tworzenia się korka nie jest jasno zdefiniowane. Zarządcy, po długich obradach, postanowili zautomatyzować cały proces według własnych ustaleń. Przed każdym zjazdem z autostrady zainstalowane zostaną fotokomórki, które przekazywać będą do systemu wartości kolejnych sekund, w których zarejestrowane zostaną przejeżdżające pojazdy. Ustalono także, że każdy taki pojazd, drogę od fotokomórki do bramki poboru opłat pokona średnio w 30 sekund. Bramki będą otwierane wtedy i tylko wtedy, gdy na odcinku drogi od fotokomórki do bramek, liczba pojazdów poruszających się będzie większa niż liczba bramek. Teraz wystarczy już tylko napisać program, który będzie sterował automatycznie bramkami, a dokładniej, wyznaczy przedziały czasowe z dokładnością do sekundy, w których bramki będą otwarte i wolne od poboru opłat.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita b (1 ≤ b ≤ 10) oznaczająca liczbę bramek na zjeździe. W wierszu drugim i ostatnim podany jest niemalejący ciąg liczb całkowitych (1 ≤ t_i ≤ 10⁶) o nieznanej długości, oznaczający wartości kolejnych sekund, w których fotokomórka zarejestrowała poruszający się pojazd. Długość ciągu (liczba zarejestrowanych pojazdów) nie przekracza 10⁵ wyrazów.

Wyjście
Na wyjściu należy wypisać przedziały czasowe [a - b), gdzie a i b to wartości sekund początku i końca przedziału, w którym bramki będą otwarte. Każdy przedział w osobnym wierszu.


Przykład

Wejście
4
3 5 5 7 34 34 36 37 38 53 60 60 68 79 79 79 82 99 100 110 120 130 130 131 131

Wyjście
[34 - 35)
[38 - 67)
[79 - 98)
[99 - 109)
[131 - 150)

Wyjaśnienie do przykładu.
W 34-tej sekundzie fotokomórkę miną dwa pojazdy i na odcinku drogi od czujnika do bramek będzie znajdowało się pięć pojazdów w ruchu. Taka sytuacja potrwa sekundę, bo w 35-tej sekundzie dwa pojazdy, które zarejestrowała fotokomórka w piątej sekundzie, po upływie trzydziestu sekund, opuszczą autostradę i pozostaną tylko trzy pojazdy w ruchu. Zatem od 34-tej sekundy, przez jedną sekundę, bramki będą otwarte, co zapisujemy przedziałem [34 - 35).
Kolejny przedział, w którym będzie więcej pojazdów w ruchu niż bramek na sprawdzanym odcinku drogi rozpocznie się w 38-mej sekundzie i potrwa 29 sekund do początku 67-mej sekundy, wtedy na odcinku drogi pozostaną w ruchu cztery pojazdy, które już korka nie tworzą. Analogicznie powstały kolejne przedziały w podanym przykładzie.