题目：

题目描述

为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到最低的物品位置 P1，并把从左起第 1 个至第 P1 个之间的物品反序；第二次找到第二低的物品的位置 P2，并把左起第二个至第 P2 个之间的物品反序……最终所有的物品都会被排好序。 

上图给出一个示例，第一次操作前，最低物品在位置 4，于是把第 1 至第 4 个物品反序；第二次操作前，第二低的物品在位置 6，于是把第 2 至第 6 的物品反序……

你的任务是编写一个程序，确定操作序列，即每次操作前第 i 低的物品所在的位置Pi，以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后他们的相对位置关系与初始时相同。 

输入格式

第一行包含一个正整数 n，表示需要排序的物品数量。 

第二行包含 n 和空格分隔的整数 ai，表示每个物品的高度。 

输出格式

输出一行包含 n 个空格分隔的整数 Pi。 

样例数据 1

输入　 []

 

 

6 

3 4 5 1 6 2

输出

4 6 4 5 6 6

样例数据 2

输入　 []

 

 

4 

3 3 2 1

输出

4 2 4 4

备注

【数据范围】

对于 30% 的数据：1≤n≤1000 

对于 100% 的数据：1≤n≤100000，1≤ai≤2×109 

心得：

　　利用splay进行区间反转模版题：若要反转i-j内的区间（包括i，j）先找到下标为i-1的点splay到根节点，再找到j+1的点splay到i-1下方，将j+1的左子树的子树进行swap即可（注意打标记）

代码：

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;const int N=100005;int father[N],son[N][2],tag[N],size[N],root,tot,num[N];int n,rank[N];struct node{ int x,id;}a[N];int R(){ char c;int f=0; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) f=(f<<3)+(f<<1)+c-'0'; return f;}bool cmp(node a,node b){ if(a.x!=b.x) return a.x
                 
                  ed) swap(st,ed); l=find(st);r=find(ed); splay(l,0);splay(r,root); tag[son[son[root][1]][0]]^=1; } return 0;}