[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}$。

3
12 5 8 3 15 8 0

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