[POI2009] ARC-Architects
题目描述
给定一个序列 $a_i$($1\leq a_i\leq 10^9$)且 $1\leq i\le n$ 且 $n\leq
1.5\times 10^7$,和一个整数 $k$($k\leq n$ 且 $k\leq 10^6$),求出 $a$ 的一个长度为 $k$ 的子序列 $a_{b_i}$ 满足:
1. $1\leq b_1\leq b_2\leq \ldots\leq b_k$
2. 在满足 $1$ 的情况下 $a_{b_1}, a_{b_2},\ldots , a_{b_k}$ 字典序最大。
输入输出格式
输入格式
第一行一个数 $k$,以下一行,为序列 $a_i$。以一个单独的 $0$ 结束。
输出格式
$k$ 行,每行一个数,其中第 $i$ 行为 $a_{b_i}$。
输入输出样例
输入样例 #1
3
12 5 8 3 15 8 0
输出样例 #1
12
15
8
说明
本题原为交互题,为了正常评测,你需要[下载](http://oi.edu.pl/static/attachment/20110704/oi16-etap2-arc.zip)后解压,并把etap2/arc/prog里的carclib.c贴到程序之前。
### 评测方式
首先请按 `说明/提示` 中说的做
然后将 `#include "carclib.h"` 去掉
将第一次输入改为 `=inicjuj()` 形式,将之后的每一次输入改为 `=wczytaj()` 形式,将输出改为 `wypisz(jakoscProjektu)` 形式(`jakoscProjektu` 代表你输出的数)
最后切记不能开O2