Cho số nguyên dương n. In biểu diễn nhị phân của n.

Input

13

Output

1101

Cho một xâu ký tự (S) chỉ gồm các chữ cái tiếng Anh thường.

Thực hiện phép biến đổi sau cho đến khi không thể tiếp tục:

• Nếu tồn tại hai ký tự giống nhau đứng liền kề nhau thì xóa cả hai ký tự đó khỏi xâu.

Sau mỗi lần xóa, các phần còn lại của xâu được ghép lại với nhau và có thể tạo ra những cặp ký tự giống nhau mới cần tiếp tục xóa.

Hãy xác định xâu cuối cùng thu được.

Dữ liệu vào

• Gồm một dòng chứa xâu (S).

Dữ liệu ra

• Xâu còn lại sau khi thực hiện toàn bộ các phép xóa.
• Nếu xâu trở thành rỗng, ghi ra dòng trống.

Ví dụ 1

abbaca

ca

Giải thích

abbaca
→ aaca      (xóa bb)
→ ca        (xóa aa)

Không còn hai ký tự giống nhau đứng cạnh nhau.

Ví dụ 2

INPUT

azxxzy

OUTPUT

ay

Giải thích

azxxzy
→ azzy      (xóa xx)
→ ay        (xóa zz)

Ràng buộc

• (~1 \le |S| \le 10^6~)
• Xâu chỉ gồm các ký tự từ 'a' đến 'z'.

Yêu cầu

Xây dựng chương trình có độ phức tạp thời gian (O(n)).

Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Với mỗi phần tử, tìm phần tử lớn hơn đầu tiên bên phải.

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 phần tử lớn hơn đầu tiên bên phải ứng với từng phần tử ~a_i~, nếu không tìm thấy thì in ra -1.

Ví dụ

Input

5
2 1 2 4 3

Output

4 2 4 -1 -1

Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Với mỗi phần tử, tìm phần tử lớn hơn đầu tiên bên trái.

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 phần tử lớn hơn đầu tiên bên trái ứng với từng phần tử ~a_i~, nếu không tìm thấy thì in ra -1.

Ví dụ

Input

5
2 1 2 4 3

Output

-1 2 -1 -1 4

Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Với mỗi phần tử, tìm phần tử nhỏ hơn đầu tiên bên trái.

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 phần tử nhỏ hơn đầu tiên bên trái ứng với từng phần tử ~a_i~, nếu không tìm thấy thì in ra -1.

Ví dụ

Input

5
2 1 2 4 3

Output

-1 -1 1 2 2

Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Với mỗi phần tử, tìm phần tử nhỏ hơn đầu tiên bên phải.

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 phần tử nhỏ hơn đầu tiên bên phải ứng với từng phần tử ~a_i~, nếu không tìm thấy thì in ra -1.

Ví dụ

Input

5
2 1 2 4 3

Output

1 -1 -1 3 -1

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

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

3 2 3 5 5

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 trái a[i] sao đoạn từ i đến j a[i] vẫn đạt giá trị bé 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 tráii a[i] sao đoạn từ i đến j a[i] vẫn đạt giá trị bé nhất.

Ví dụ

Input

5
2 1 2 4 3

Output

1 1 3 4 4

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