UOJ Logo Universal Online Judge

UOJ

#143. 【UER #5】万圣节的数列

统计

红包是一个热爱数学的男孩子。今天是万圣节,红包正在家里捣鼓一个长度为 $n$ 数列。

这时候一群熊孩子们敲开了红包家的门,他们高呼着“不用给糖,只要捣蛋”的口号把红包的数列打乱了。这让红包很难过,于是他打算恢复这个数列。

但是因为这个数列实在是太长了,所以他已经不记得这个数列原来是什么样的了。于是他采用了一个折中的方法:把数列恢复成他最喜欢的样子。

对于一个数列 $A_1, A_2, \dots, A_n$ 和一个数列 $B_1, B_2, \dots, B_m$,若存在一组 $p_1, p_2, \dots, p_m$ 满足 $1 \leq p_1 < p_2 < \dots < p_m \leq n$ 且对于任意的 $1 \leq i \leq m$ 有 $B_i = A_{p_i}$,则称 $B$ 是 $A$ 的子序列。若 $B$ 对于任意 $1 < i < m$ 还满足 $B_i - B_{i - 1} = B_{i + 1} - B_i$ 则称 $B$ 是 $A$ 的等差子序列。

红包不喜欢等差数列,于是一个数列的等差子序列数量越少,他越喜欢。

现在他把被打乱后的数列 $A$ 交给了你,你需要将 $A$ 中元素重新排列得到使得等差子序列数量最少,两个等差子序列不同当且仅当 $m$ 不同或者存在 $k$ 使得 $p_k$ 不同。

输入格式

第一行是一个正整数 $n$,表示数列的长度。

第二行是 $n$ 个正整数,表示 $A_1, A_2, \dots, A_n$。

输出格式

仅一行,输出 $n$ 个整数 $p_1, p_2, \dots, p_n$。其中第 $i$ 个数 $p_i$ 表示重新排列后的数列中第 $i$ 个元素在原数列 $A$ 中是第 $p_i$ 个元素。

如果存在多种满足条件的方案,输出任意一个就行。

样例一

input

6
1 3 3 3 4 5

output

2 1 6 4 3 5

explanation

你恢复的数列是:$\{3, 1, 5, 3, 3, 4\}$,它的等差子序列是所有长度小于等于 $2$ 的子序列和 $\{3, 3, 3\}$。

样例二

见样例数据下载。

限制与约定

测试点编号$n$ 的规模其他约定
1$n \leq 10$
2
3$n \leq 500$$A_i \leq 10$
4
5$A$ 是一个 $1$ 到 $n$ 的排列
6
7
8
9
10

对于所有数据,都有 $A_i \leq 10^9$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载