CF873E.Awards For Contestants

Alexey recently held a programming contest for students from Berland. n students participated in a contest, i-th of them solved a__i problems. Now he wants to award some contestants. Alexey can award the students with diplomas of three different degrees. Each student either will receive one diploma of some degree, or won't receive any diplomas at all. Let cnt__x be the number of students that are awarded with diplomas of degree x (1 ≤ x ≤ 3). The following conditions must hold:

• For each x (1 ≤ x ≤ 3) cnt__x > 0;
• For any two degrees x and y cnt__x ≤ 2·cnt__y.

Of course, there are a lot of ways to distribute the diplomas. Let b__i be the degree of diploma i-th student will receive (or  - 1 if i-th student won't receive any diplomas). Also for any x such that 1 ≤ x ≤ 3 let c__x be the maximum number of problems solved by a student that receives a diploma of degree x, and d__x be the minimum number of problems solved by a student that receives a diploma of degree x. Alexey wants to distribute the diplomas in such a way that:

1. If student i solved more problems than student j, then he has to be awarded not worse than student j (it's impossible that student j receives a diploma and i doesn't receive any, and also it's impossible that both of them receive a diploma, but b__j < b__i);
2. _d_1 - _c_2 is maximum possible;
3. Among all ways that maximize the previous expression, _d_2 - _c_3 is maximum possible;
4. Among all ways that correspond to the two previous conditions, _d_3 - c - 1 is maximum possible, where c - 1 is the maximum number of problems solved by a student that doesn't receive any diploma (or 0 if each student is awarded with some diploma).

Help Alexey to find a way to award the contestants!

阿列克谢最近为来自贝尔兰的学生举办了一场编程竞赛。共有 $n$ 名学生参赛，其中第 $i$ 名学生解决了 $a_i$ 道题目。现在他希望奖励其中一部分参赛者。阿列克谢可以颁发三种不同等级的证书（即一等、二等、三等证书）。每名学生至多获得一张证书（即获得某一等级的证书，或不获得任何证书）。令 $cnt_x$ 表示获得等级为 $x$ 的证书的学生人数（$1 \le x \le 3$）。需满足以下条件：

• 对每个 $x$（$1 \le x \le 3$），均有 $cnt_x > 0$；
• 对任意两个等级 $x$ 和 $y$，均有 $cnt_x \le 2 \cdot cnt_y$。

显然，满足上述条件的证书分配方式有很多。设 $b_i$ 表示第 $i$ 名学生所获证书的等级（若未获任何证书，则 $b_i = -1$）。此外，对每个 $x$（$1 \le x \le 3$），记 $c_x$ 为所有获得等级 $x$ 证书的学生中解题数的最大值，$d_x$ 为其中解题数的最小值。阿列克谢希望以如下方式分配证书：

1. 若学生 $i$ 解决的题目数多于学生 $j$，则学生 $i$ 的获奖等级不得低于学生 $j$（即：不可能出现学生 $j$ 获得证书而学生 $i$ 未获任何证书的情况；也不可能出现两人均获得证书但 $b_j < b_i$ 的情况）；
2. 在所有可行方案中，最大化 $d_1 - c_2$；
3. 在所有使上式取最大值的方案中，再最大化 $d_2 - c_3$；
4. 在所有同时满足前两个条件的方案中，再最大化 $d_3 - c_{-1}$，其中 $c_{-1}$ 表示所有未获得任何证书的学生中解题数的最大值（若所有学生均获得证书，则 $c_{-1} = 0$）。

请帮助阿列克谢找出一种满足要求的颁奖方案！

The first line contains one integer number n (3 ≤ n ≤ 3000).

The second line contains n integer numbers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 5000).

第一行包含一个整数 $ n $（$ 3 \leq n \leq 3000 $）。

第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 5000 $）。

Output n numbers. i-th number must be equal to the degree of diploma i-th contestant will receive (or  - 1 if he doesn't receive any diploma).

If there are multiple optimal solutions, print any of them. It is guaranteed that the answer always exists.

输出 $n$ 个数。其中第 $i$ 个数必须等于第 $i$ 位参赛者所获文凭的等级（若未获得任何文凭，则为 $-1$）。

若存在多个最优解，输出任意一个即可。题目保证答案一定存在。