Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Với mỗi phần tử, 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ị nhỏ 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:

• In ra 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ị nhỏ nhất.

Ví dụ

Input

5
2 1 2 4 3

Output

1 5 5 4 5