Cake Distribution Challenge

Three inseparable friends, Little B, Little Y and Little Z, have received n pieces of cake. The i-th cake weighs \(a_i\). Cakes cannot be cut; each cake must be given whole to one of the three friends and no cake may be wasted.

Although they are selfless and do not mind if someone gets less cake, they follow the principle that ideology is above friendship. Therefore, they must distribute the cakes so that for any two friends, the sum of their cake weights is strictly greater than the cake weight of the remaining friend. In mathematical terms, if the total weight received by the three friends are \(S_1\), \(S_2\) and \(S_3\) respectively, the following must hold:

[ \begin{cases} S_1+S_2 > S_3,\ S_1+S_3 > S_2,\ S_2+S_3 > S_1. \end{cases} ]

This condition is equivalent to requiring that the maximum of \(S_1,S_2,S_3\) is strictly less than \(\frac{S}{2}\), where \(S = S_1+S_2+S_3\).

Your task is to either find a valid distribution of the cakes to the three friends or determine that no such distribution exists.

Note: The friends are identified by numbers 1, 2, and 3 (corresponding to Little B, Little Y, and Little Z respectively). The answer (if it exists) should output "YES" on the first line and on the second line output n integers, where the i-th integer (1, 2, or 3) tells which friend gets the i-th cake from the input order. If no valid distribution exists, simply output "NO".

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (the number of cakes).
• The second line contains \(n\) positive integers \(a_1, a_2, \ldots, a_n\) representing the weight of each cake.

outputFormat

If a valid distribution exists, output "YES" on the first line. On the second line, print \(n\) space-separated integers, each of which is 1, 2, or 3; the i-th number indicates which friend receives the i-th cake. If no valid distribution exists, output "NO".

sample

3
3 4 2

YES
2 1 3