class Tree{
	   elemtype info;
    int par;
};

class Tree{
	   elemtype info;
    node* child;
};

class  TreeNode{
	   elemtype info;
    TreeNode *FirstChild,*NextSibling;
};

class TreeNode{
	elemtype data;
  TreeNode *lchild,*rchild;
  TreeNode(elemtype D,TreeNode *lc=NULL,TreeNode *rc=NULL){
  	data=D;
  	lchild=lc;
  	rchild=rc;
  }
};

/*
前序遍历
*/
void PreTra(TreeNode *T){
    if(T==NULL)return;
    cout<<T->data;//此处对结点进行操作
    PreTra(T->lchild);
    PreTra(T->rchild);
    return;
}

/*
中序遍历
*/
void InTra(TreeNode *T){
    if(T==NULL)return;
    InTra(T->lchild);
    cout<<T->data;//此处对结点进行操作
    InTra(T->rchild);
    return;
}

/*
后序遍历
*/
void PosTra(TreeNode *T){
    if(T==NULL)return;
    PosTra(T->lchild);
    PosTra(T->rchild);
    cout<<T->data;//此处对结点进行操作
    return;
}

/*
层序遍历
*/
void LevelTra(TreeNode *T){
    if(T==NULL)return;
    queue<TreeNode*> Q;
    Q.push(T);
    while(!Q.empty()){
    	TreeNode *S=Q.front();
    	Q.pop();
        cout<<S->data;//对元素进行操作
        if(S->lchild))Q.push(S->lchild);
        if(S->rchild))Q.push(S->rchild);
    }
    return;
}

/*
假设已经构建好二叉树T，构建中序线索树
*/
TreeNode *pre=NULL;//用于前驱线索的构建
void InitTheading(Tree *T){
		if(T){
				InitTheading(T->lchild);
				//L
				if(T->ltag==1) T->lchild=pre;//前驱
				if(pre && pre->rtag==1) pre->rchild=T;//后继
				pre=T;
				//N
				InitTheading(T->lchild);
				//R
		}
		return;
}

//前驱：
  if (p->ltag==1) pre=p->lchild;
  else //如图
//后继：
  if (p->rtag==1) next=p->rchild;
  else{
      if (p->ltag==0) next=p->lchild;
      else next=p->rchild;
  }

//前驱：
  if (p->ltag==1) pre=p->lchild;
  else {
  	pre=p->lchild;
  	while(pre->rchild){
  	     pre=pre->rchild;
      }
  }
//后继：
  if (p->rtag==1) next=p->rchild;
  else{
    next=p->rchild;
        while(next->lchild){
  	     next=next->lchild;
      }
  }

//前驱：
  if (p->ltag==1) pre=p->lchild;
  else {
  	if(p->rtag==0)pre=p->rchild;
  	else pre=p->lchild;
  }
//后继：
  if (p->rtag==1) next=p->rchild;
  else //如图

class TreeNode{
		int weight;
		int par;
		int lc,rc;
};

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
 
class TreeNode{
	public:
	   int info,par,lc,rc;
	   TreeNode(){
        info=0; 
        par=lc=rc=-1;
	   }
};

void FindMin(int &min1,int &min2,int k,TreeNode *num){
//找到当前已有结点（0~k）中无父结点中最小的两个结点A、B
	for(int i=0;i<k;i++){
	   if(num[i].par==-1){
	       if(num[min1].info>num[i].info){
	           min1=i;
		  }
	   }
	}
	for(int i=0;i<k;i++){
	   if(num[i].par==-1 && i!=min1){
	       if(num[min2].info>num[i].info){
		      min2=i;
		  }
    }
	}
	return;
}

int main(){
    int n;
    cin>>n;
    TreeNode num[2*n-1];
    for(int i=0;i<n;i++)
    {
	       cin>>num[i].info;
    }
    num[2*n-1].info=1000;
    int min1=2*n-1,min2=2*n-1;
    for(int i=0;i<n-1;i++){
	//- 更新已有结点个数：k+=1,将以上步骤循环n-1次.
    FindMin(min1,min2,n+i,num);
	   num[min1].par=n+i;
	   num[min2].par=n+i;
	   num[n+i].info=num[min1].info+num[min2].info;
	   num[n+i].lc=min1;
	   num[n+i].rc=min2;
//第k+1个结点的权值为A与B的权值之和，令其左右子结点分别为A、B。
	   min1=min2=2*n-1;
	}
    for(int i=0;i<2*n-1;i++){
	       cout<<i<<"\t"<<num[i].info<<"\t"<<num[i].par<<"\t"<<num[i].lc<<"\t"<<num[i].rc<<endl;
    }
    return 0;
}

void BST_insert(Node *T,Node *S )//结点S插入二叉查找树T中
{
    if(T == NULL)
    { 
        T=S;
        return;
    }
    Node *p,*q;
    int key = S->data;
    p = T;
    while(p)
    {
        q = p;
        if(p->data == key)
        {
            return;
        }
        else if(p->data > key){
            p = p->rchild;
        }
        else
        {
            p = p->lchild; 
        }
    }
    if(q->data < key) S = q->lchild;
    else S = q->rchild;
    return;
}

void BST_delete(Node *T,int key)
{
    if(!T)return;
    Node *p,*q;
    bool tag=0;//tag=0表示删除结点为左子树，tag=1表示删除结点为右子树
    p = T;
    while(p)
    {
        q=p;
        if(p->data == key)
        {
            break;
        }
        else if(p->data > key){
            p = p->rchild;
            tag = 1;
        }
        else
        {
            p = p->lchild; 
            tag = 0;
        }
    }
    if(p -> lchild == NULL && p->rchild == NULL)
    {
        //叶结点
        tag? q->rchild = NULL : q->lchild = NULL;
        delete p;
    }
    else 
    {
        if(p -> lchild == NULL){
            tag ? q->rchild = p->rchild : q->lchild = p->rchild;
            delete p;
            return;
        }
        else if(p -> rchild == NULL){
            tag ? q->rchild = p->lchild : q->lchild = p->lchild;
            delete p;
            return;
        }
        else 
        {
            Node *lc = p->lchild, *rc = p->rchild;
            delete p;
            p = lc;
            if(! p->rchild)
            {
                tag ? q->rchild = p : q->lchild = p;
                p->rchild = rc;
                return;
            }
            Node *r = p;
            while(p -> rchild)/找到左子树的最右子结点
            {
                r=p;
                p = p->rchild;
            }
            tag ? q->rchild = p : q->lchild = p;
            r->rchild = p->lchild; //注意将最右子节点的左子树连接到其父节点上
            p->rchild = rc;
            p->lchild = lc; 
            return;
        }
    }
}

class Node{
	elemtype data;
	int bal;
  Node *lchild,*rchild;
  Node(elemtype D,TreeNode *lc=NULL,TreeNode *rc=NULL){
  	data=D;
  	lchild=lc;
  	rchild=rc;
  	bal = 0;
  }
};

void RotateL(Node *p, Node *par, int tag)//p为结点A，par为其父结点，tag为par-p的连接方式
{
    Node *prc = p->rchild;//C
    p->rchild = prc->lchild;//A->D
    prc->lchild = p;
    //此时子树发生变化了的结点有A和C，只需要改变AC的平衡因子即可
    p->bal = prc->bal = 0;
    tag ? par->rchild = prc : par->lchild = prc;//更新par的子结点 
}

void RotateR(Node *p, Node *par, int tag)//p为结点A，par为其父结点，tag为par-p的连接方式
{
    Node *plc = p->lchild;//B
    p->rlhild = plc->rchild;//A->E
    plc->rchild = p;
    //此时子树发生变化了的结点有A和B，只需要改变AB的平衡因子即可
    p->bal = plc->bal = 0;
    tag ? par->rchild = prc : par->lchild = prc;//更新par的子结点 
}

class AdjMatrix{
    int mat[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};

class MGraph{
    VertexType vexs[MAX_VERTEX_NUM]; //顶点表
    AdjMatrix arcs; //邻接矩阵
    int vexnum,arcnum; //图的顶点数和弧数
};

// 边结点（链式）
class EdgeNode {
 public:
	int adjvex; //这条边指向哪个顶点
	int weight;	//权值
	EdgeNode* next; //指向下一条依附该顶点的边
};
// 顶点结构
class VertexNode {
 public:
	int value; //顶点的值
	EdgeNode *firstedge;	//指向第一条依附该顶点的边
};
// 图结构
class GraphList {
 public:
	VertexNode adjList[N]; //顶点信息
	int numVertex; //顶点数
	int numEdges; //边数
};

void createGraph(GraphList* g){
	int v,e;
	cin>>v>>e;
	g->numVertex=v;
	g->numEdges=e;
	//图的顶点与边的个数，构建图
	for(int i=0;i<v;i++){
		cin>>g->adjList[i].value;
	}//各个顶点的值，构建顶点
	for(int i=0;i<e;i++){
		int vi,vj,w;
		cin>>vi>>vj>>w;
		EdgeNode* newe=new EdgeNode;//创建一条新的边
		newe->weight=w;//边的权值
		newe->adjvex=vj;//边指向vj
		EdgeNode *p;
		p=g->adjList[vi].firstedge; //这条边以vi开头
		if(p==NULL){
		  g->adjList[vi].firstedge=newe;
		}
		else {
		  while(p->next != NULL){
		      p=p->next;
		  }
		  p->next=newe;
		}//将这条边连接至边结点的最后
	}//构建边
}

int count[g->numVertex];//统计入度
for(int i=0;i<g->numVertex;i++){
  	count[i]=0;
}
for(int i=0;i<g->numVertex;i++){
	   EdgeNode *p=g->adjList[i].firstedge;
	   while(p){
		  count[p->adjvex]++;
		  p=p->next;
	   }
}

/*
图以邻接表形式储存
*/
void DFS(GraphList *g,int i,int *visited){
	cout<<g->adjList[i].value<<" "; //访问该点
	visited[i]=1;//已访问标记
	EdgeNode *p;
	p=g->adjList[i].firstedge;//找到该点的第一个邻接点
	while(p!=NULL){
		if(visited[p->adjvex]==0)
		  DFS(g,p->adjvex,visited);//当该邻接点未被访问时，递归访问该邻接点
		p=p->next;//寻找下一个邻接点
	}
}

void DFSTraverse(GraphList *g){
	int *visited= new int [g->numVertex];
	for(int i=0;i<g->numVertex;i++){
	   visited[i]=0;
	} //visited数组记录点是否已经访问
	for(int i=0;i<g->numVertex;i++){//依次访问图中顶点
	   if(visited[i]==0)DFS(g,i,visited);//当该点没被访问过，进行深度优先搜索
	}
	delete [] visited;
}

/*
图以邻接表形式储存
*/
void BFS(GraphList *g,int i,int *visited){
	cout<<g->adjList[i].value<<" "; //访问该顶点
	visited[i]=1;	//已访问标记
	queue<int> q;	
	q.push(i); //将起始点入队
	while(!q.empty()){
	//每个while循环将一个顶点出队，并依次访问其所有邻接点
		int w=q.front();
		q.pop();
		EdgeNode *p;
		p=g->adjList[w].firstedge;//用于访问所有邻接点
		while(p!=NULL){//访问邻接链表中的所有邻接点
			if(visited[p->adjvex]==0){
				cout<<g->adjList[p->adjvex].value<<" "; //访问该顶点
				visited[p->adjvex]=1;//已访问标记
				q.push(p->adjvex);
			}
			p=p->next;
		}
	}
}

void BFSTraverse(GraphList *g){
	int *visited= new int [g->numVertex];
	for(int i=0;i<g->numVertex;i++){
		visited[i]=0;
	}//visited数组记录点是否已经访问
	for(int i=0;i<g->numVertex;i++){
		if(visited[i]==0)BFS(g,i,visited);//依次对未被访问过的顶点进行广度优先搜索
	}
	delete [] visited;
}

class closedge{
	int lowcost,adjvex;
};//辅助数组

class TreeNode{
	int vi,vj;
	int weight;
};//生成树

class closedge{
	int lowcost,adjvex;
};//辅助数组

class TreeNode{
	int vi,vj;
	int weight;
};//生成树

void Prim(GraphList G, MST& T, int u ) {//u为起点 
	float lowcost[G.NumVertices];
	int nearvex[G.NumVertices];
	for ( int i = 0; i < G.NumVertices; i++ ) {
		lowcost[i] = G.Edge[u][i]; //Vu到各点代价
		adjvex[i] = u; //及最短带权路径
	} 
	adjvex[u] = -1; //加到生成树顶点集合
	int k = 0; //存放最小生成树的结点
	for ( i = 0; i < G.NumEdges-1; i++ )//循环n-1次, 加入n-1条边
  {
		if ( i != u ) 
    { 
				EdgeData min = MaxValue; 
		int v = 0;
		for ( int j = 0; j < NumVertices; j++ )
			if ( adjvex[j] != -1 && lowcost[j] < min )
      { // =-1不参选
				v = j; 
				min = lowcost[j]; 
			}
		//求生成树外顶点到生成树内顶点具有最小权值的边, v是当前具最小权值的边
		if ( v ) 
    { //v=0表示再也找不到要求顶点
			T[k].tail = adjvex[v]; //选边加入生成树
			T[k].head = v;
			T[k].cost = lowcost[v];
			k++; 
			adjvex[v] = -1; //该边加入生成树标记
			for ( j = 0; j < G.n; j++ )
			if ( adjvex[j] != -1 && G.Edge[v][j] < lowcost[j] ) 
      {
				lowcost[j] = G.Edge[v][j]; //修改
				adjvex[j] = v;
			}
		} 
	}
} 

typedef int Vertex;//顶点信息 
struct Edge//边的信息 
{
	Vertex begin;
	Vertex end;
	int edge;//边的权值 
};

int n;//顶点数 
int m;//边的数目
Edge Graph[5000];//以边存储图 
int pre[110];//并查集基本操作 
int sum;//最小的生成树权值和

void Init()
{
	for(int i=1;i<=n;i++)
	{
		pre[i]=i;
	}
}

int find(int x)
{
	int r=x;
	while(pre[r]!=r)
		r=pre[r];
	int i=x,j;
	while(i!=r)
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}

void join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		pre[fx]=fy;
}
bool comp(Edge a,Edge b)//对边权值进行排序 
{
	return a.edge<b.edge;
}
void Kruskal() 
{
	sort(Graph,Graph+m,comp);//排序，最小权值的边最先 
	int number=0; //记录当前用于连接顶点的边数 
	Init();//初始化并查集 
	sum=0;
	for(int i=0;i<m;i++)
	{
		if(number==n-1)//n个顶点若连接n-1条边，则图已经连通 
			break;
		if(find(Graph[i].begin)!=find(Graph[i].end))//当前边所连接的顶点处于未连通的状态 
		{
			join(Graph[i].begin,Graph[i].end);
			sum+=Graph[i].edge;
			number++;
		}
	}
}

void Graphcircle(GraphList *g){
	int count[g->numVertex],del[g->numVertex];
		for(int i=0;i<g->numVertex;i++){
			count[i]=0;
		}
	for(int i=0;i<g->numVertex;i++){
		EdgeNode *p=g->adjList[i].firstedge;
		while(p){
			count[p->adjvex]++;
			p=p->next;
		}
	}//初始化count,得到所有顶点的入度
	stack<int> sta;
	int num=0;
	for(int i=0;i<g->numVertex;i++){
		if(count[i]==0){
			sta.push(i);
		}
	}//将初始时所有入度为0的顶点入栈 
	while(!sta.empty()){
		int w=sta.top();
		sta.pop();//弹出一个顶点，对其进行操作
		//cout<<g->adjList[w].value; //输出排序
		num++;//统计弹出顶点数
		EdgeNode *p=g->adjList[w].firstedge;//访问该顶点的邻接点
		while(p){
			count[p->adjvex]--;
      if(count[p->adjvex]==0){
         sta.push(p->adjvex);
      }//更新剩余顶点的入度，并马上判断是否有新的顶点入度为0
			p=p->next;
		}
	} 
	 if(num==g->numVertex) cout<<"no circle";//无环，得到拓扑排序
	 else cout<<"has circle";//有环
}

void AOE(){
	int n,m;
	cin>>n>>m;
	int mat[n][n],ve[n],vl[n],e[m],l[m],edge[m][2];
	for(int i=0;i<n;i++){
		ve[i]=-1;
		vl[i]=999;
		for(int j=0;j<n;j++)
			mat[i][j]=0;
	}
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		mat[a][b]=w;
		edge[i][0]=a;
		edge[i][1]=b;
	}
	
	//拓扑 
	int count[n];
	for(int i=0;i<n;i++){
        count[i]=0;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(mat[i][j]>0)count[j]++;
		}
	}
	stack<int> sta,last;
	int num=0;
	for(int i=0;i<n;i++){
		if(count[i]==0){
			sta.push(i);
			ve[i]=0;
		}
	}//第一个入栈 
	while(!sta.empty()){
		int w=sta.top();
		sta.pop();
    last.push(w);
		for(int i=0;i<n;i++){
			if(i!=w && mat[w][i]!=0){
				count[i]--;
				ve[i]=max(ve[i],ve[w]+mat[w][i]);
				if(count[i]==0)
					sta.push(i);
       }    
		}
	}
	int w=last.top();
	vl[w]=ve[w];
	while(!last.empty()){
		int w=last.top();
		last.pop();
		for(int i=0;i<n;i++){
			if(i!=w && mat[i][w]!=0){
				vl[i]=min(vl[i],vl[w]-mat[i][w]);
			}			   
		}
	}
	
	for(int i=0;i<m;i++){
		e[i]=ve[edge[i][0]];
		l[i]=vl[edge[i][1]]-mat[edge[i][0]][edge[i][1]];
	} 
	
	for(int i=0;i<n;i++){
		cout<<ve[i]<<"\t";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<vl[i]<<"\t";
	}cout<<endl;
	
	for(int i=0;i<m;i++){
		cout<<e[i]<<"\t";
	}
	cout<<endl;
	for(int i=0;i<m;i++){
		cout<<l[i]<<"\t";
	}
	cout<<endl;
	return 0;
}

void Dijkstra(){
	int n,m,v;//顶点数n、边数m、起点v 
	cin>>n>>m>>v;
	int mat[n][n];//邻接矩阵 
	int dist[n],path[n],S[n];//三个辅助数组 
	for(int i=0;i<n;i++){
		dist[i]=0;
		path[i]=-1;
		S[i]=0;
		for(int j=0;j<n;j++)
			mat[i][j]=0;
	}//数组初始化 
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		mat[a][b]=w;
	}//邻接矩阵输入 
	dist[v]=0;
	path[v]=v;
	S[v]=1;
	for(int i=0;i<n;i++){
		if(mat[v][i]>0){
				dist[i]=mat[v][i];
				path[i]=v;
		}
	}//算法初始化 
//	for(int j=0;j<n;j++){
//		cout<<dist[j]<<"\t";
//	}
//	cout<<endl;
//	for(int j=0;j<n;j++){
//		cout<<path[j]<<"\t";
//	}
//	cout<<endl;
//输出检测
	for(int i=0;i<n-1;i++){//执行n-1个循环，依次确定每个点的最短路径 
		int min=999,min_ind=0;
		for(int j=0;j<n;j++){
			if(S[j]==0){
				if(min>dist[j]){
					min=dist[j];
					min_ind=j;
				}
			}
		}//找到未得到最小路径的点中的最小值
		S[min_ind]=1;//该点确定最小路径，添加至S
		for(int j=0;j<n;j++){
			if(mat[min_ind][j]>0){
				if(dist[j]>(dist[min_ind]+mat[min_ind][j])){
					dist[j]=dist[min_ind]+mat[min_ind][j];//修改路径长度 
					path[j]=min_ind;//标记路径 
				}
			}
		}
	}
    return 0;
}

void Floyd(){
	int n,m;//顶点数n、边数m
	cin>>n>>m;
	int mat[n][n];//邻接矩阵 
	int path[n][n];//三个辅助数组 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			mat[i][j]=999;
			path[i][j]=-1;
		}
		mat[i][i]=0;
		path[i][i]=i;
	}//数组初始化 
	for(int i=0;i<m;i++){
		int a,b,w;
		cin>>a>>b>>w;
		mat[a][b]=w;
		path[a][b]=a;
	}//算法初始化 
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				//当新的路径更加短时，更新mat和path
				if(mat[i][j]>mat[i][k]+mat[k][j]){
					mat[i][j]=mat[i][k]+mat[k][j];
					path[i][j]=path[k][j];
				}
			}
    }
	}
//	for(int i=0;i<n;i++){
//		for(int j=0;j<n;j++){
//			cout<<mat[i][j]<<"\t";
//		}
//		cout<<endl;
//	}
//	cout<<endl;
//输出检测
	return 0;
}

int Seq_Search(SSTable ST , KeyType key){ 
    int p ; 
    ST. elem[0].key=key ; /* 设置监视哨兵,失败返回0 */
    for (p=ST.length; !EQ(ST. elem[p].key, key); p--)
    return(p) ; 
} 

int Bin_Search(SSTable ST , KeyType key){ 
    int Low=1,High=ST.length, Mid ;
    while (Low<High){ 
        Mid=(Low+High)/2 ;
        if (EQ(ST. elem[Mid].key, key)) 
        return(Mid) ; 
        else if (LT(ST. elem[Mid].key, key)) 
        Low=Mid+1 ;
        else High=Mid-1 ;
    }
    return(0) ; /* 查找失败 */ 
}

class Index{ 
    keyType maxkey ; /* 块中最大的关键字 */
    int startpos ; /* 块的起始位置指针 */
};

int Block_search(
RecType ST[ ] , 
Index ind[ ] , 
KeyType key , 
int n , 
int b
){ 
/* 在分块索引表中查找关键字为key的记录 */ 
 /*表长为n ，块数为b */
    int i=0 , j , k ;
    while ((i<b)&&LT(ind[i].maxkey, key) ) 
        i++ ;
    if (i>b) { 
        printf(“Not found”); 
        return(0); 
    }
    j=ind[i].startpos ;
    while ((j<n)&&LQ(ST[j].key, ind[i].maxkey) ){ 
        if ( EQ(ST[j].key, key) ) break ;
        j++ ;
    } /* 在块内查找 */
    if (j>n||!EQ(ST[j].key, key) ){ 
        j=0; 
        printf(“\nNot found”); 
    }
    return(j); 
}

void HeapAdjust(HeapType &H,int s,int m){ 
    ElemType rc=H.r[s];
    for (int j=2*s;j<=m;j*=2){ //从当前结点开始，依次操作子结点
        if ((j<m) && (H.r[j].key<H.r[j+1].key))
            ++j;
        if (rc.key > H.r[j].key) break;//满足大顶堆
        H.r[s].key=H.r[j].key; 
        s=j;
    }
    H.r[s]=rc;
}

/*
主函数
*/
for (int i=H.length/2; i>0; --i)//从n/2开始操作
    HeapAdjust(H,i,H.length);

#define NULLKEY -1 
/* 根据关键字类型定义空标识 */
typedef struct
{ KeyType key ; /* 关键字域 */
otherType otherinfo ; /* 记录的其它域 */
}RecType ;

int Hash_search(RecType HT[], KeyType k, int m)
/* 查找散列表HT中的关键字K,用开放定址法解决冲突 */
{ int h, j ;
h=h(k) ;
while (j<m && !EQ(HT[h].key, NULLKEY) )
{ if (EQ(HT[h].key, k) ) return(h) ;
else h=R(k, ++j) ; 
}
return(-1) ;
}

#define M 15
typedef struct node
{ KeyType key;
struct node *link;
}HNode;

void InsertSort(SqList &L){
    for(int i=2 ; i<=L.length ; i++){
        if(L.r[i].key < L.r[i-1].key){
            L.r[0] = L.r[i]; // 监视哨
            int j=i-1;
            for(; L.r[0].key < L.r[j].key && j>0; j—){
                L.r[j+1] = L.r[j];
            }//依次向后移位
            L.r[j+1]=L.r[0];
        }
    }
}

void ShellSort(int *num, int dlta[] , int t){
    //dlta[]={5,3,2,1};
    for(int k = 0 ; k < t ; k++){
        ShellSort(num,dlta[k]);
    }
}

void ShellSort(int* num,int k){
	int temp;
	for(int i=k+1; i<n ;i++){
		if(num[i] < num[i-k]){
			temp = num[i];//监视哨
			int j = i-k;
			for(; j>=0 && temp < num[j];j-=k ){//条件为>=0且需要移动
				num[j+k] = num[j];
			}
			num[j+k]=temp;	
		}
	}
}

void BubbleSort(int* num){
	int temp;
	bool change=1;
	for(int i=0; i<n-1 && change;i++){
		change=0;
		for(int j=1;j<n-i;j++){
			if(num[j]<num[j-1]){
				swap(num[j],num[j-1]);
				change=1; 
			}
		}
	}
}

void QuickSort(int R[],int low,int high)
{
    int i,j,temp;
    i=low;
    j=high;
    if(low<high)
    {
        temp=R[low];//设置枢轴
        while(i!=j)
        {
            while(i<j && R[j]>=temp)//枢轴为左边的值时，从右边开始寻找
            {
                --j;
            }
            if(i<j)//找到小于枢轴量的值，交换
            {
                R[i]=R[j];
                ++i;
            }

           while(i<j && R[i]<temp)//从左边开始寻找
            {
                ++i;
            }
            if(i<j)//找到大于枢轴量的值，交换
            {
                R[j]=R[i];
                --j;
            }
        }
        R[i]=temp;//结束是i、j为枢轴量的位置
        QuickSort(R,low,i-1);
        QuickSort(R,i+1,high);
    }
}

void SelectSort(SqList &L){ 
    int len = arr.length;
    int minIndex, temp;
    for (int i = 0; i < len - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        swap(arr[i],arr[minIndex]);
    }
    return arr;
}

void Merge(int r[],int r1[],int s,int m,int t)
{
    int i=s;
    int j=m+1;
    int k=s;
    while(i<=m && j<=t)
    {
        if(r[i]<=r[j])
            r1[k++]=r[i++];
        else
            r1[k++]=r[j++];
    }
    while(i<=m)
        r1[k++]=r[i++];
    while(j<=t)
        r1[k++]=r[j++];
    for(int l=0; l<8; l++)
        r[l]=r1[l];
}
 
void MergeSort(int r[],int r1[],int s,int t)
{
    if(s==t)
        return;
    else
    {
        int m=(s+t)/2;
        MergeSort(r,r1,s,m);//子序列排序
        MergeSort(r,r1,m+1,t);//子序列排序
        Merge(r,r1,s,m,t);//该序列排序
    }
}