Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Ứ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 phải a[i] sao đoạn từ i đến j 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 phải a[i] sao đoạn từ i đến j a[i] vẫn đạt giá trị lớn nhất.

Ví dụ

Input

5
2 1 2 4 3

Output

2 2 3 5 5