{"problem":{"name":"E. Awards For Contestants","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF873E"},"statements":[{"statement_type":"Markdown","content":"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:\n\n*   For each _x_ (1 ≤ _x_ ≤ 3) _cnt__x_ > 0;\n*   For any two degrees _x_ and _y_ _cnt__x_ ≤ 2·_cnt__y_.\n\nOf 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:\n\n1.  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_);\n2.  _d_1 - _c_2 is maximum possible;\n3.  Among all ways that maximize the previous expression, _d_2 - _c_3 is maximum possible;\n4.  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).\n\nHelp Alexey to find a way to award the contestants!\n\n## Input\n\nThe first line contains one integer number _n_ (3 ≤ _n_ ≤ 3000).\n\nThe second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 5000).\n\n## Output\n\nOutput _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).\n\nIf there are multiple optimal solutions, print any of them. It is guaranteed that the answer always exists.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Alexey 最近为来自 Berland 的学生举办了一场编程竞赛。#cf_span[n] 名学生参加了比赛，其中第 #cf_span[i] 名学生解决了 #cf_span[ai] 道题目。现在他希望给一些参赛者颁发奖状。Alexey 可以颁发三种不同等级的奖状。每个学生要么获得一个某种等级的奖状，要么不获得任何奖状。设 #cf_span[cntx] 表示获得等级为 #cf_span[x]（#cf_span[1 ≤ x ≤ 3]）奖状的学生人数。必须满足以下条件：\\n\\n当然，分配奖状的方式有很多。设 #cf_span[bi] 表示第 #cf_span[i] 名学生将获得的奖状等级（若该学生未获得任何奖状，则为 #cf_span[ - 1]）。同时，对于任意满足 #cf_span[1 ≤ x ≤ 3] 的 #cf_span[x]，设 #cf_span[cx] 为获得等级为 #cf_span[x] 奖状的学生中解决题目数的最大值，#cf_span[dx] 为获得等级为 #cf_span[x] 奖状的学生中解决题目数的最小值。Alexey 希望以如下方式分配奖状：\\n\\n帮助 Alexey 找到一种分配奖状的方式！\\n\\n第一行包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 3000]）。\\n\\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 5000]）。\\n\\n请输出 #cf_span[n] 个数字。第 #cf_span[i] 个数字必须等于第 #cf_span[i] 名参赛者将获得的奖状等级（若未获得奖状，则为 #cf_span[ - 1]）。\\n\\n如果有多个最优解，输出任意一个即可。题目保证答案一定存在。\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 3000]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 5000]）。\"},{\"iden\":\"output\",\"content\":\"请输出 #cf_span[n] 个数字。第 #cf_span[i] 个数字必须等于第 #cf_span[i] 名参赛者将获得的奖状等级（若未获得奖状，则为 #cf_span[ - 1]）。如果有多个最优解，输出任意一个即可。题目保证答案一定存在。\"},{\"iden\":\"examples\",\"content\":\"输入\\n4\\n1 2 3 4\\n输出\\n3 3 2 1\\n\\n输入\\n6\\n1 4 3 1 1 2\\n输出\\n-1 1 2 -1 -1 3 \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 3 \\leq n \\leq 3000 $, be the number of contestants.  \nLet $ A = (a_1, a_2, \\dots, a_n) $, where $ a_i \\in \\mathbb{Z} $, $ 1 \\leq a_i \\leq 5000 $, be the number of problems solved by contestant $ i $.  \n\nLet $ b_i \\in \\{-1, 1, 2, 3\\} $ denote the diploma degree assigned to contestant $ i $, where $ b_i = -1 $ means no diploma.  \nLet $ \\text{cnt}_x = |\\{ i \\mid b_i = x \\}| $ for $ x \\in \\{1,2,3\\} $, the number of students receiving diploma of degree $ x $.  \nLet $ c_x = \\max \\{ a_i \\mid b_i = x \\} $, $ d_x = \\min \\{ a_i \\mid b_i = x \\} $ for $ x \\in \\{1,2,3\\} $, the maximum and minimum scores among recipients of diploma degree $ x $.  \n\n**Constraints**  \n1. $ \\text{cnt}_1 \\geq 1 $, $ \\text{cnt}_2 \\geq 1 $, $ \\text{cnt}_3 \\geq 1 $.  \n2. $ c_1 > c_2 > c_3 $.  \n3. $ d_1 > d_2 > d_3 $.  \n4. $ c_1 > d_1 \\geq c_2 > d_2 \\geq c_3 > d_3 $.  \n\n**Objective**  \nFind any assignment $ b = (b_1, b_2, \\dots, b_n) \\in \\{-1,1,2,3\\}^n $ satisfying the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF873E","tags":["brute force","data structures","dp"],"sample_group":[["4\n1 2 3 4","3 3 2 1"],["6\n1 4 3 1 1 2","\\-1 1 2 -1 -1 3"]],"created_at":"2026-03-03 11:00:39"}}