Considerând K un număr natural, vom numi permutare de mărime K o aranjare într-o ordine oarecare a elementelor mulțimii {1,2,..,K}. Ana găsește scris pe o foaie de hârtie, un șir de numere naturale v = (v[1],v[2],v[3],...,v[N])

Plecând de la acest șir, Ana numește secvență a lui v, un subșir de numere care apar pe poziții consecutive în șirul inițial. De exemplu, șirul 5 7 8 9 1 6 conține secvența 8 9 1, secvența 7 8 9 1 6, dar nu conține secvența 8 9 6.

Anei îi vine ideea să încerce să verifice dacă șirul de numere poate fi împărțit în secvențe care reprezintă permutări de diferite mărimi.

De exemplu, dacă Ana găsește șirul v =(2, 1, 4, 1, 3, 2), atunci ea îl poate împărți în două secvențe de permutări astfel: secvența v[1], v[2] respectiv secvența v[3] , v[4], v[5], v[6].

Dacă Ana găsește șirul v =( 1, 2, 2, 3) atunci nu va putea obține o împărțire în secvențe de permutări.

Cerința

Realizați un program care citește un șir de N numere naturale și rezolvă următoarea cerință:

• determină o împărțire a acestuia în secvențe de permutări. Dacă există mai multe soluții se va afișa soluția minim lexicografică.

Dacă șirul poate fi împărțit în secvențe de permutări, pentru fiecare număr din șir, în ordinea v[1], .., v[N], se va afișa numărul permutării din care face parte.

Numerotarea permutărilor se va face consecutiv începând cu numărul 1.

Date de intrare

Fișierul de intrare perm.in conține pe prima linie numărul natural N, iar pe a doua linie, un șir format din N numere naturale separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire perm.out va conține pe prima linie mesajul NU dacă șirul nu se poate împărți în secvențe de permutări. Dacă împărțirea se poate efectua atunci pe prima linie se va scrie numărul secvențelor de permutări obținut, iar pe a doua linie un șir de numere reprezentând împărțirea minim lexicografică determinată. Numerele pe linia a doua vor fi separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ v[i] ≤ 20 000
• Pentru două șiruri de N numere a[1],a[2],..a[N] și b[1],b[2],..b[N] spunem ca șirul a este mai mic lexicografic decât șirul b, dacă există un indice j, cu 1 ≤ j < N, astfel încât a[1]=b[1], a[2]=b[2], …, a[j]=b[j] și a[j+1]<b[j+1]

Exemplul 1

perm.in

10
2 1 3 4 1 1 2 3 4 5

perm.out

3
1 1 1 1 2 3 3 3 3 3

Explicație

Prima secvență care reprezintă o permutare e formată din primele 4 elemente, a doua din elementul de pe poziția 5, iar a treia din ultimele 5 elemente.

Exemplul 2

perm.in

4
1 2 2 3

perm.out

NU