You are given an array ~A~ of ~N~ integers. For every position ~i~ (from ~0~ to ~N-1~), find the greatest value among all elements to its right. That is, find the maximum element in the subarray ~A[i+1 \dots N-1]~.

If no element exists to the right (i.e., for the last element), the answer is ~-1~.

Input Format

The first line contains a single integer ~N~. The second line contains ~N~ space-separated integers representing the array ~A~.

Output Format

Print ~N~ space-separated integers, where the ~i~-th integer is the greatest value to the right of ~A[i]~.

Example

Input

6
17 18 5 4 6 1

Output

18 6 6 6 1 -1

Constraints

• ~1 \le N \le 200000~
• ~1 \le A[i] \le 10^9~

Subtasks

• 50% of the tests satisfy ~N \le 2000~.
• 50% of the tests use the full constraints.