#P2215. [HAOI2007] 上升序列

    ID: 1231 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp贪心递推各省省选2007河南

[HAOI2007] 上升序列

题目描述

对于一个给定的 S={a1,a2,a3,,an}S=\{a_1,a_2,a_3,…,a_n\} , 若有 P={ax1,ax2,ax3,,axm}P=\{a_{x_1},a_{x_2},a_{x_3},…,a_{x_m}\} , 满足 (x1<x2<<xm)(x_1<x_2<…<x_m)(ax1<ax2<<axm)(a_{x_1}<a_{x_2}<…<a_{x_m}) 。那么就称 PPSS 的一个上升序列。如果有多个 PP 满足条件,那么我们想求字典序最小的那个。

任务:

给出 SS 序列,给出若干询问。对于第 ii 个询问,求出长度为 LiL_i 的上升序列,如有多个,求出字典序最小的那个(即首先 x1x_1 最小,如果不唯一,再看 x2x_2 最小……),如果不存在长度为 LiL_i 的上升序列,则打印 Impossible

输入格式

第一行一个 NN,表示序列一共有 NN 个元素。

第二行 NN 个数,为 a1,a2,,ana_1, a_2 , \cdots , a_n

第三行一个 MM,表示询问次数。下面接 MM 行每行一个数 LL,表示要询问长度为 LL 的上升序列。

输出格式

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

6
3 4 1 2 3 6
3
6
4
5
Impossible
1 2 3 6
Impossible
6
6 7 1 2 3 4
1
2
6 7

提示

N10000N \le 10000M1000M \le 1000,保证数据随机。