Description：

给出 $S$ 序列，给出若干询问。对于第 $ i $ 个询问，求出下标字典序最小的长度为 $L_i$ 的上升序列。

$1\le n \le 10000$ $1\le m \le 1000$

Solution：

想预处理一些东西发现空间开不下，又不能每次不停向后找字典序最小的，会超时。

于是不每次找字典序最小的合法的下一个转移，而是把合法的先存下来，如果有字典序更小的再来更新它，合法的含义是存在一个长度大于等于剩余长度的上升子序列，且这个数字大于上一个数字。于是开一个栈记录当前的情况，对于新加进来的一个数，如果合法且更优，就不停弹栈。最后判断栈内元素个数是否为 $k$ 即可判断有无解。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

int a[MAXN];

int f[MAXN];

int b[MAXN],s[MAXN];

bool cmp(int x,int y){return a[x] < a[y];}

int tot = 0;

int lowbit(int x){return x&(-x);}

int c[MAXN];

void add(int p,int x){for(int i = p;i >= 1;i -= lowbit(i))c[i] = max(c[i],x);return;}

int query(int p){int res = 0;for(int i = p;i <= n;i += lowbit(i))res = max(res,c[i]);return res;}

int q[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)b[i] = i;

	sort(b + 1,b + 1 + n,cmp);

	for(int i = 1;i <= n;++i)

		if(a[b[i]] != a[b[i - 1]])s[b[i]] = ++tot;

		else s[b[i]] = tot;

	for(int i = n;i >= 1;--i)

	{

		f[i] = query(s[i] + 1) + 1;

		add(s[i],f[i]);

	}

	scanf("%d",&m);

	int k;

	memset(q,0,sizeof(q));

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&k);

		int head = 1,tail = 0;

		for(int p = 1;p <= n;++p)

		{

			while(head <= tail && f[p] >= k - (tail - head + 1) + 1 && p < q[tail] && a[p] > a[q[tail - 1]])q[tail--] = 0;

			if(f[p] >= k - (tail - head + 1) && a[p] > a[q[tail]])q[++tail] = p;

		}

		if(tail - head + 1 < k)puts("Impossible");

		else

		{

			for(int p = 1;p <= k;++p)

			{

				printf("%d ",a[q[head]]);

				++head;

			}

			puts("");

		}

	}

	return 0;

}