Description

　　对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax2 < … < axm)，那么就称P为S的一个上升序列。

如果有多个P满足条件，那么我们想求字典序最小的那个。

任务给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.

Input

　　第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。

下面接M行每行一个数L，表示要询问长度为L的上升序列。N<=10000，M<=1000

Output

　　对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.

Sample Input

6

3 4 1 2 3 6

3

6

4

5

Sample Output

Impossible

1 2 3 6

Impossible

---

题解Here!

首先要把最长不下降子序列求出来。

设$dp[i]$表示以$i$结尾的最长不下降子序列的长度，$f[i]$表示最长不下降子序列的长度为$i$的最后一个元素的值。

这个时候用$O(n\log_2n)$的算法预处理$dp[i]$和$f[i]$。

那，怎么判断呢？

我们发现，我们从左到右扫，若存在$dp[i]>=l\&\&A[i]<B[j]$，则$j$为$i$的后一个。

然后就没了。

附代码：

#include
      
       #include
       
        #include
        
         #define MAXN 10010using namespace std;int n,m,s=1;int A[MAXN],B[MAXN],f[MAXN],dp[MAXN];inline int read(){	int date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}int main(){	n=read();	for(int i=1;i<=n;i++){		A[i]=read();		B[n-i+1]=A[i];	}	f[1]=B[1];	dp[1]=1;	for(int i=2;i<=n;i++){		int l=1,r=s,mid;		while(l<=r){			mid=l+r>>1;			if(f[mid]>B[i])l=mid+1;			else r=mid-1;		}		f[l]=B[i];		dp[i]=l;		s=max(s,l);	}	for(int i=1;i<=n/2;i++)swap(dp[i],dp[n-i+1]);	m=read();	while(m--){		int l=read(),last=-1;		if(s
         
          =l&&A[i]>last){			last=A[i];			l--;			printf("%d ",A[i]);		}		printf("\n");	}	return 0;}