本题思路:
根据题意 为了求出最大值 显然是要让大的数字尽可能的出现在左边 然而由于卡牌堆的缘故 如果大的数字在牌堆下方的话 就要连着最大数字上面的牌一起取走 那么该怎么去取卡牌呢???

如果每次都去找最大的数字那么o(n2) 必然会超时
那么通过观察我们可以发现每次取当前的最大值出去即可

以1 5 2 4 3为例 设当前的最大值为1 往后遍历发现 5>1 那么将5之前的数字放入栈中 再以5为当前的最大值再往后遍历 5之后没有比他大的了 那么将5 2 4 3一起放入栈中 从右往左放 再加上之前的1 就变成了 1 3 4 2 5 出栈时从右往左出站 输出 5 2 4 3 1


同理 以4 2 5 3 6 1为例 当前的最大值为4 往后遍历发现5>4 那么将5之前的数字 4 2入栈为 2 4 ,再往后遍历发现6 > 5那么将 6之前的数字入栈 入栈为3 5 继续遍历那么6就是最大的值了 将6和1 入栈 入栈为 1 6那么合起来就是
2 4 3 5 1 6 再从右往左出栈即为 6 1 5 3 4 2

题目描述

You have a deck of n cards, and you’d like to reorder it to a new one.

Each card has a value between 1 and n equal to pi. All pi are pairwise distinct. Cards in a deck are numbered from bottom to top, i. e. p1 stands for the bottom card, pn is the top card.

In each step you pick some integer k>0, take the top k cards from the original deck and place them, in the order they are now, on top of the new deck. You perform this operation until the original deck is empty. (Refer to the notes section for the better understanding.)

Let’s define an order of a deck as ∑i=1nnn−i⋅pi.

Given the original deck, output the deck with maximum possible order you can make using the operation above.

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains the single integer n (1≤n≤105) — the size of deck you have.

The second line contains n integers p1,p2,…,pn (1≤pi≤n; pi≠pj if i≠j) — values of card in the deck from bottom to top.

It’s guaranteed that the sum of n over all test cases doesn’t exceed 105.

Output
For each test case print the deck with maximum possible order. Print values of cards in the deck from bottom to top.

If there are multiple answers, print any of them.

样例

Example
inputCopy
4
4
1 2 3 4
5
1 5 2 4 3
6
4 2 5 3 6 1
1
1
outputCopy
4 3 2 1
5 2 4 3 1
6 1 5 3 4 2
1


Note
In the first test case, one of the optimal strategies is the next one:

take 1 card from the top of p and move it to p′: p becomes [1,2,3], p′ becomes [4];
take 1 card from the top of p: p becomes [1,2], p′ becomes [4,3];
take 1 card from the top of p: p becomes [1], p′ becomes [4,3,2];
take 1 card from the top of p: p becomes empty, p′ becomes [4,3,2,1].
In result, p′ has order equal to 43⋅4+42⋅3+41⋅2+40⋅1 = 256+48+8+1=313.
In the second test case, one of the optimal strategies is:

take 4 cards from the top of p and move it to p′: p becomes [1], p′ becomes [5,2,4,3];
take 1 card from the top of p and move it to p′: p becomes empty, p′ becomes [5,2,4,3,1];
In result, p′ has order equal to 54⋅5+53⋅2+52⋅4+51⋅3+50⋅1 = 3125+250+100+15+1=3491.
In the third test case, one of the optimal strategies is:

take 2 cards from the top of p and move it to p′: p becomes [4,2,5,3], p′ becomes [6,1];
take 2 cards from the top of p and move it to p′: p becomes [4,2], p′ becomes [6,1,5,3];
take 2 cards from the top of p and move it to p′: p becomes empty, p′ becomes [6,1,5,3,4,2].
In result, p′ has order equal to 65⋅6+64⋅1+63⋅5+62⋅3+61⋅4+60⋅2 = 46656+1296+1080+108+24+2=49166.

C++ 代码

#include <iostream>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N];
void push(stack<int> &s, int l, int r) //从l到r入栈
{
    for (int i = r; i >= l; i--)//（从右往左入）
        s.push(a[i]);
}
/*打印栈*/
void prt(stack<int> &s)
{
    while (s.size())
    {
        printf("%d ", s.top());
        s.pop();
    }
    puts("");
}
int main()
{
    int N;
    cin >> N;
    while (N--) //N组数据
    {
        stack<int> s;
        int n;
        scanf("%d",&n);
        for (int i = 0; i < n; i++)
           scanf("%d",&a[i]);
        a[n] = n + 1; //最后设置一个最大的数，保证前面所有都比它小
        int M = a[0], last = 0;
        for (int i = 0; i <= n; i++)
        {
            if (a[i] > M) 
            {
                push(s, last, i - 1); //入栈并更新
                last = i; 
                M = a[i];
            }
        }
        prt(s); //输出结果
    }
    return 0;
}