h2. Date de ieşire

În fişierul de ieşire $blaturi.out$ se va scrie, pe prima linie, costul minim pentru a pregăti cele N blaturi.

În fişierul de ieşire $blaturi.out$ se va scrie, pe prima linie, costul minim pentru a pregăti cele N blaturi iar pe a doua linie o secvenţă de N valori ‘1’ sau ‘2’. Dacă a i-a valoare este ‘1’ înseamnă că al i-lea blat a fost pregătit de primul coleg, respectiv de al doilea coleg dacă valoarea este ‘2’.
 

h2. Restricţii
* $1 ≤ N ≤ 100.000$

* $Se garantează că pentru 20% din teste 1 ≤ N ≤ 10$
* $Costul suplimentar este acelaşi indiferent de timpul de preparare al blatului.$
* $Este posibil ca un coleg să pregătească singur toate blaturile.$

* $Dacă există mai multe secvenţe care dau timpul minim, se va afişa cea mai mică din punct de vedere lexicografic.$

h2. Exemplu

1 2 3 4
2 1
3 3|23

1 1 1 1

|
h3. Explicaţie