IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005

Opis

W Patentolandii Anty-Patentowcy codziennie ślą tysiące listów do Głównego Patenta (odpowiednik prezydenta) oraz do Wielkich Firm Lobbystycznych. Korespondencja ta jest bardzo ważna, ponieważ dzięki niej sekretarki Głównego Patenta mają pracę, a Wielkie Firmy Lobbystyczne czują, że są wielkie. Anty-Patentowcom bardzo dużo czasu zajmuje pisanie tych listów i upłynie jeszcze dużo wody, zanim wpadną na pomysł napisania programu do automatycznego generowania listów. Bardzo chciałbyś napisać taki program, ale nie masz czasu, ponieważ Anty-Patentowcy wciąż nękają Cię nowymi zadaniami.

Tym razem wymyślili, ze wreszcie trzeba zoptymalizować pracę nad korespondencją. Oto kilka faktów, które pozwolą Ci lepiej zrozumieć problem: Dana osoba prowadzi korespondencję z N różnymi firmami. Z góry wiadomo, ze do i-tej firmy wyśle L[i] listów i dostanie tyle samo listowych odpowiedzi. Pisanie jednego listu zajmuje dokładnie 1 dzień. Czytanie listu (odpowiedzi) zajmuje też dokładnie 1 dzień (to są bardzo długie listy). Co więcej, zauważono, że od momentu wysłania listu do momentu przyjścia odpowiedzi upływają zawsze dokładnie 3 dni (czyli cała procedura trwa 5 dni - 1 dzień pisania, 3 dni wolne, 1 dzień czytania). Naturalnie nie można napisać następnego listu do danej firmy, jeśli nie dostało się odpowiedzi na poprzedni (ale tych 3 dni oczekiwania nie trzeba marnować - w tym czasie można korespondować z innymi firmami). Trzeba też wiedzieć, że w momencie gdy list przychodzi należy go od razu przeczytać (nie wolno odkładać czytania listu na później, bo listy pisane są specjalnym atramentem, który bardzo szybko znika). Twoim zadaniem jest takie uszeregowanie korespondencji z firmami, aby korespondencja z firmami skończyła się jak najszybciej.

Wejście

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita oznaczająca liczbę następujących zestawów danych.

W pierwszej i jedynej linii zestawu danych znajduje się liczba całkowita 3≤N≤1000000, oznaczająca liczbę Wielkich Firm Lobbystycznych, z którymi trwa korespondencja. Następnie znajduje się N liczb całkowitych 1≤L[i]≤1000000, oznaczających liczbę listów, które należy wysłać do i-tej firmy. Przy czym, należy założyć, iż suma{L[i]}≤1000000 oraz max{L[i]}≤1/3*suma{L[i]}.

Wyjście

Dla każdego zestawu danych należy wypisać jedną linię. Pierwszą liczbą w linii powinna być minimalna liczba dni D potrzebnych na korespondencję z firmami. Następne D liczb całkowitych opisuje kolejne dni: Liczba 0 oznacza dzień wolny, natomiast liczba i (1<i<N) oznacza korespondencję (pisanie lub czytanie) z i-tą firmą. Jeżeli istnieje wiele różnych korespondencji trwających minimalną liczbę dni, należy wypisać dowolne z nich.

Przykładowe wejście

2
4 1 1 1 1
3 1 1 1

Przykładowe wyjście

8 1 2 3 4 1 2 3 4
7 3 2 1 0 3 2 1