Cho số nguyên dương ~n~ và mảng ~a[1..n]~.

Yêu cầu: Ứng với mỗi phần tử a[i], hãy tìm vị trí j của phần tử xa nhất bên trái a[i] sao đoạn từ j đến i a[i] vẫn đạt giá trị lớn nhất.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương n (~1 \le n \le 10^5~)

• Ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~)

Dữ liệu ra:

• Ứng với mỗi phần tử a[i], hãy tìm vị trí j của phần tử xa nhất bên trái a[i] sao đoạn từ j đến i a[i] vẫn đạt giá trị lớn nhất.

Ví dụ

Input

5
2 1 2 4 3

Output

1 2 1 1 5