Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

C. Sandwiched Jenga
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The fat sheep and his tiger friend is given a tower of $$$N$$$ distinct Jenga blocks stacked vertically. The blocks are numbered from bottom to top, and the weight of the $$$i$$$-th block from the bottom is $$$w_i$$$. All weights are distinct.

You want to build a second tower by repeatedly removing blocks from the original tower.

A block is considered stable if:

  • If it has both a block above and below it, its weight is strictly less than both adjacent blocks.
  • The top block is always stable.
  • The bottom block is stable if and only if its weight is strictly less than the block above it.
  • A single remaining block in the tower is always stable.

You repeatedly perform the following operation until the original tower becomes empty:

  • Choose any stable block.
  • Remove it from the original tower.
  • Place it on top of your second tower.

Let the resulting second tower be described from bottom to top by the sequence of weights of the removed blocks in the order they were placed.

Your task is to determine the lexicographically greatest possible second tower (from bottom to top) that can be achieved.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

  • The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$).
  • The second line contains $$$N$$$ distinct integers $$$w_1, w_2, \ldots, w_N$$$ ($$$1 \le w_i \le 10^9$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

Print $$$N$$$ integers representing the lexicographically greatest possible second tower from bottom to top.

Examples
Input
1
4
10 6 9 5
Output
6 5 9 10
Input
4
3
3 10 8
3
14 5 1
6
1 2 3 4 5 6
1
100
Output
8 10 3
1 5 14
6 5 4 3 2 1
100