[POI2009]Arc

时间限制:50s      空间限制:162MB

题目描述

给定一个序列{ai | 1 <= ai <= 1000000000 且 1 <= i <= n 且 n <= 15000000}和一个整数 k (k <= n 且 k <= 1000000),求出a的一个长度为k的子序列{a[bi]}满足: (1) 1 <= b1 <= b2 <= ... <= bk (2) 在满足(1)的情况下 {a[b1], a[b2], ... , a[bk]} 字典序最大。


输入格式

第一行一个数k,以下一行,为序列ai。以一个单独的0结束


输出格式

k行,每行一个数,其中第i行为a[bi]。


样例输入

12
5 8 3 15 8 0

样例输出

12
15
8

提示

按照这里:http://main.edu.pl/en/archive/oi/16/arc
来写交互式的程序,然后把这个东西:http://oi.edu.pl/static/attachment/20110704/oi16-etap2-arc.zip
解压后把etap2/arc/prog里的carclib.c的内容贴到自己的源码中的一大堆“include”之前。这样这个程序就从交互式程序变成普通的程序了,就可以AC了。
鸣谢vfleaking


题目来源

没有写明来源