brick

Problem Description

Rar the Cat has arranged a row of N bricks. The i^th brick from the left has height A_i.

Peanut comes along and attempts to stack these bricks. Going from the leftmost brick to the rightmost, he stacks bricks using the following rules:

• Let the current brick be of height X.
• While there is at least 1 brick in the stack, he will remove the topmost brick from the stack if it is smaller than or equals to X. This process is repeated until there is no more bricks in the stack, or the topmost brick is larger than X.
• Add the current brick of height X to the top of the stack.

By doing so, Peanut will get a stack of bricks with increasing height (top to bottom) at the end of the day. Rar the Cat is curious and wants to know what is in the stack. However, Peanut does not want to let Rar the Cat see the stack. Can you help Rar the Cat find out what is in the stack?

Limits

For all testcases, 0 ≤ A_i ≤ 10⁹.

Subtask 1 (23%): 1 ≤ N ≤ 500.

Subtask 2 (28%): 1 ≤ N ≤ 5000.

Subtask 3 (49%): 1 ≤ N ≤ 500000.

Subtask 4 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array A.

Output

The output should contain the heights of the bricks in the stack. The height of the topmost brick should be printed first, one height per line.

Sample Testcase 1

Input

10
1 2 9 5 7 6 3 4 2 2

Output

2
4
6
7
9

Explanation

Sample Testcase 2

Input

5
5 4 3 2 1

Output

1
2
3
4
5

Sample Testcase 3

Input

5
1 2 3 4 5

Output

5

Sample Testcase 4

Input

5
4 3 2 1 5

Output

5