Widoczność

Niech dany będzie ciąg liczb całkowitych nieujemnych a1, ..., an. Mówimy, że element ai ogranicza widoczność elementowi aj, jeżeli i < j, ai > aj, ale żaden spośród elementów ai+1, ..., aj-1 nie jest większy od aj.

Dla każdego wyrazu ciągu znajdź wyraz, który ogranicza mu widoczność, jeżeli taki istnieje.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (2 <= n <= 500000), oznaczająca długość ciągu. Kolejnych n wierszy zawiera po jednej liczbie całkowitej ai (0 <= ai <= 109). Wyrazy ciągu numerujemy liczbami całkowitymi od 1 do n.

Wyjście

Wyjście powinno składać się z n wierszy. i-ty wiersz powinien zawierać jedną liczbę całkowitą, równą indeksowi wyrazu ciągu, który ogranicza widoczność wyrazowy i-temu, albo -1, jeżeli takie wyraz nie istnieje.

Przykład

Dla danych wejściowych:

6
8
4
2
5
7
8

Poprawnym wynikiem jest:

-1
1
2
1
1
-1