Żołnierze

Limit pamięci: 256 MB

W szeregu stoi żołnierzy, ponumerowanych kolejno od 1 do (od lewej do prawej). Generał będzie wydawał żołnierzom polecenie o nazwie obiad. Jeśli generał wyda to polecenie żołnierzowi o numerze , żołnierz ten będzie musiał najpierw wypowiedzieć na głos numer żołnierza, który stoi z jego lewej strony, potem wypowiedzieć numer żołnierza, który stoi z jego prawej strony, a następnie udać się czym prędzej na obiad. Kiedy żołnierz znika z szeregu, pozostali żołnierze nieco się przesuwają, tak żeby w szeregu nie pozostała żadna dziura.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę żołnierzy. Każdy z kolejnych wierszy zawiera po jednej liczbie całkowitej z zakresu od 1 do . Liczba zapisana w -tym wierszu oznacza numer żołnierza, któremu w -tym poleceniu generał rozkazał iść na obiad. Liczby w wierszach nie powtarzają się.

Wyjście

Twój program powinien wypisać wierszy. -ty z tych wierszy powinien zawierać dwie liczby całkowite: numery lewego i prawego sąsiada żołnierza, który w -tym poleceniu udaje się na obiad. Jeśli ów żołnierz w rozważanym momencie nie ma lewego lub prawego sąsiada, jako numer odpowiedniego sąsiada należy wypisać .

Przykład

Dla danych wejściowych:

5
4
2
1
5
3

poprawną odpowiedzią jest:

3 5
1 3
-1 3
3 -1
-1 -1