Cho mảng \(A[]\) có \(n\) phần tử, nhiệm vụ của bạn là đối với mỗi phần tử \(A[i]\) trong mảng phải tìm ra phần tử nhỏ hơn đầu tiên nằm bên phải của phần tử lớn hơn đầu tiên nằm bên phải của \(A[i]\). Đối với những phần tử không có phần tử lớn hơn bên phải thì in ra \(-1\).

Ví dụ \(A[] = \{1, 5, 3, 3, 4, 1\}\): \(1 \to 5 \to 3\), \(5 \to -1 \to -1\), \(3 \to 4 \to -1\), \(3 \to 4 \to -1\), \(4 \to -1 \to -1\), \(1 \to -1 \to -1\).

Input

• Dòng đầu tiên chứa \(N\): số lượng phần tử trong mảng.
• Dòng thứ hai chứa \(N\) số nguyên, mỗi số cách nhau một khoảng trắng.

Constraints

• \(1 \leq N \leq 10^6\)
• \(1 \leq A[i] \leq 10^6\)

Output

• In ra đáp án của bài toán trên \(1\) dòng.

Example

5
11 18 12 18 10

12 -1 10 -1 -1