Alexey 最近为来自 Berland 的学生举办了一场编程竞赛。 n 个学生参加了一场竞赛,其中 i 个学生解决了人工智能问题。现在他想给一些参赛者颁奖。 Alexey可以向学生颁发三个不同学位的文凭。每个学生要么会获得某种学位的文凭,要么根本不会获得任何文凭。令cntx 为获得x 级文凭的学生人数(1 ≤ x ≤ 3)。必须满足以下条件:
- 对于每个 x (1 ≤ x ≤ 3) cntx > 0;
- 对于任意两度 x 和 y cntx ≤ 2·cnty。
当然,文凭的发放方式有很多种。令 bi 为第 i 个学生将获得的文凭学位(如果第 i 个学生不会获得任何文凭,则为 - 1)。同样,对于任何满足 1 ≤ x ≤ 3 的 x,令 cx 为获得 x 学位的学生解决的问题的最大数量,dx 为获得 x 学位的学生解决的问题的最小数量。 Alexey 希望以这样的方式分发文凭:
1.如果学生i比学生j解决了更多的问题,那么他的奖励必须不比学生j差(不可能j学生获得毕业证书而i没有获得毕业证书,也不可能他们都获得毕业证书,但bj < bi);
2. d1 - c2 是可能的最大值;
3. 在所有最大化先前表达式的方法中,d2 - c3 是最大可能的;
4. 在对应于前两个条件的所有方式中,d3 - c - 1 是最大可能的,其中 c - 1 是未获得任何文凭的学生解决的问题的最大数量(如果每个学生都获得了一些文凭,则为 0)。
帮助 Alexey 找到为参赛者颁奖的方法!
输入
第一行包含一个整数 n (3 ≤ n ≤ 3000)。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 5000)。
输出
输出n个数字。第 i 个数字必须等于第 i 个参赛者将获得的文凭学位(如果没有获得任何文凭,则为 1)。
如果有多个最优解,则打印其中任意一个。保证答案总是存在。
示例
输入 #1
4 1 2 3 4
输出 #1
3 3 2 1
输入 #2
6 1 4 3 1 1 2
输出 #2
-1 1 2 -1 -1 3