Problem D
Triangeltal

Bilden motsvarar första exemplet.

I en klass med $N$ elever har det blivit dags för det obligatoriska momentet att hålla tal. De flesta av eleverna ser fram emot att hålla tal väldigt mycket, och kan knappt vänta på sin tur. Men först måste de delas in i tre grupper. Alla i grupp $1$ kommer sedan presentera för grupp $2$, grupp $2$ för grupp $3$, och grupp $3$ för grupp $1$.

Något som krånglar till den här gruppindelningen är att eleverna har olika ambitionsnivå. Varje elev $i$ kräver att få hålla tal inför minst $A_i$ personer, där $A_i$ är ett positivt heltal. Så om elev nummer $i$ exempelvis hamnar i grupp $1$, så måste grupp $2$ ha minst $A_i$ medlemmar för att elev $i$ ska bli nöjd.

Du får givet de $N$ talen $A_i$, och din uppgift är att avgöra om det finns ett sätt att dela in eleverna i tre grupper så att alla blir nöjda, och hitta i så fall en giltig indelning.

Indata

Den första raden innehåller ett heltal $N$ ($3\le N\le 5\cdot {10}^5$).

Den andra raden innehåller $N$ heltal $A_i$ ($1\le A_i\le N$).

Utdata

Om det inte finns en giltig indelning, skriv ut en enda rad med strängen “NO”.

Om det finns en giltig indelning, skriv först ut en rad med strängen “YES”. Skriv därefter ut en rad med en sträng $S$ bestående av tecknen $1$, $2$ och $3$. Tecknet på plats $i$ i denna sträng indikerar vilken grupp elev $i$ hamnade i. Om det finns flera lösningar kan du skriva ut vilken som helst.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

10
1 3 1 3 3 2 4 1 5 2

YES
3313332121

3
1 2 2

NO