假设我们知道以每个点开始到最后的最长上升序列，设为w[i]，这样首先我们在w值中取max，如果询问的值比max大，这样显然就是无解，如果小的话，我们需要求出来字典序最小的方案。
那么对于所有i，我们肯定以w[i]大于询问的值中的最小的i开始，那么假设上升序列中第一个值为i，第二个值为j，那么w[j]满足大于询问的值-1，且初始序列a中，a[j]的值要大于a[i]，且为最小的j，对于最小的我们只需要通过循环正常的枚举就行了。
那么我们现在剩下的问题就是w[i]值如何求，如果n小一些的话我们就可以n^2正常的做了，但是n为10^4，这样我们就需要维护单调队列que[i]，表示长度为i的最长上升序列中，结尾最小的值，这样就可以了。但是我们要求每个w的话需要反向枚举，然后维护下降序列就可以了。
/************************************************************** Problem: 1046 User: BLADEVIL Language: C++ Result: Accepted Time:2088 ms Memory:924 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #define maxn 10010 #define inf 20000 using namespace std; int n,tot; int a[maxn],w[maxn],que[maxn]; int combin(int x) { int l,r,mid,ans=0; l=1; r=tot; while (l<=r) { mid=(l+r)>>1; if (que[mid]>x) { ans=mid; l=mid+1; } else r=mid-1; } return ans; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); tot=1; for (int i=n;i;i--) { w[i]=combin(a[i]); //printf("%d %d|",w[i],tot); if (w[i]++==tot) tot++; que[w[i]]=(a[i]>que[w[i]])?a[i]:que[w[i]]; //for (int j=1;j<=tot;j++) printf("%d ",que[j]); printf(" "); } int maxlen=0; for (int i=1;i<=n;i++) maxlen=(w[i]>maxlen)?w[i]:maxlen; //for (int i=1;i<=n;i++) printf("%d ",w[i]); printf(" "); int m; scanf("%d",&m); while (m--) { int len; scanf("%d",&len); if (len>maxlen) { printf("Impossible "); continue; } int last=-inf; for (int i=1;i<=n;i++) if (w[i]>=len&&a[i]>last) { printf("%d",a[i]); if (len==1) { printf(" "); break; } else printf(" "),last=a[i],len--; } } return 0; }