#P18094. Iroha and the Kingdom of Construction

Iroha and the Kingdom of Construction

Iroha and the Kingdom of Construction

题目描述

有一副包含 2n2n 张牌的牌堆,牌面为 1,…,n1,\ldots,n,每种牌面恰好出现两次。

你有 260260 个初始为空的栈。按照输入顺序依次取出每张牌,并把它压入任选一个栈。

所有牌都放好后,需要能够反复执行下面的消除操作,直到所有栈都为空:选择两个不同的非空栈,若它们的栈顶牌面相同,则同时弹出这两张牌。

输出一种满足条件的入栈方案。不需要输出消除过程。

**随机输入保证:**牌序从所有“每种牌面恰好出现两次”的长度 2n2n 序列中均匀随机产生。全套评测恰好包含 5050 个测试点,包括样例。

输入格式

第一行一个整数 nn。

第二行 2n2n 个整数 a1,…,a2na_1,\ldots,a_{2n},表示从牌堆顶到底的牌面,也是取牌顺序。

输出格式

输出 2n2n 个整数 c1,…,c2nc_1,\ldots,c_{2n},其中 1≤ci≤2601\le c_i\le260,表示第 ii 张牌压入第 cic_i 个栈。

若有多种合法方案,输出任意一种。无需使用全部 260260 个栈。

数据范围

1≤n≤5×1051\le n\le5\times10^5,1≤ai≤n1\le a_i\le n,每种牌面出现恰好两次,并满足上述随机输入保证。

样例 1

输入

3
1 2 3 1 3 2

输出

1 1 1 2 2 3