8418번 - Biblioteka 다국어

Podczas wakacji Bajtazar stał się miłośnikiem dobrej literatury. Czytał bardzo dużo książek, które wypożyczał z biblioteki. Pewnego dnia odwiedził go kolega Wyjątek i zainteresował się jedną z wypożyczonych książek. Po długich namowach Bajtazar, niepomny swoich poprzednich problemów z Wyjątkiem, zgodził się wreszcie mu ją pożyczyć.

Wakacje szybko minęły. Rozpoczął się nowy rok szkolny (choć i tak w Bajtocji rozpoczyna się wyjątkowo późno - 10 Terabajta) i nadszedł czas zwrotu książek do biblioteki. Bajtazar przypomniał sobie, że jedną z nich pożyczył Wyjątkowi. Kiedy poprosił go o jej zwrot, ten przyznał się, że podczas pobytu w Kurorcie zgubił ją bawiąc się na Lollobrygidzie. Bardzo to zmartwiło biednego Bajtazara, bo wiedział, że będzie miał w związku z tym wiele nieprzyjemności.

Kiedy opowiedział o wszystkim paniom w Bibliotece, te zdecydowały, że za swoje lekkomyślne zachowanie będzie musiał ponieść karę i kazały mu przyjść w 0110 (odpowiednik naszej soboty), aby pomóc im w sortowaniu kart bibliotecznych. Jako, że kilku kolegów Bajtazara już odbyło taką karę, to karty znajdują się w wielu posortowanych plikach o różnych rozmiarach, a zadaniem Bajtazara jest połączyć je w jeden plik.

Ponieważ Bajtazar wcześniej zaplanował już sobie ten dzień, a jednocześnie nie chce znów zawieść pań bibliotekarek, musisz mu pomóc napisać program, który pozwoli mu ustalić, jak wiele czasu zajmie sortowanie kart oraz wyznaczyć stosowną kolejność łączenia plików, tak aby mógł to zrobić jak najszybciej.

Bajtazar może naraz scalić tylko dwa pliki kart. Dla uproszczenia przyjmujemy, że czas scalania dwóch plików jest równy sumie ich długości.

Napisz program, który:

• wczyta:
  • liczbę plików kart bibliotecznych, które należy scalić w jeden uporządkowany plik,
  • długości plików,
• obliczy:
  • minimalny łączny czas uporządkowania kart w bibliotece,
  • kolejność łączenia plików kart dającą ten czas,
• wypisze wynik.

Wejście składa się z dokładnie dwóch wierszy. Pierwszy wiersz zawiera liczbę n ( 2 ≤ n ≤ 100 000) plików do scalenia, w drugim wierszu znajduje się n liczb s₁, s₂,..., s_n, poodzielanych pojedynczymi odstępami, gdzie s_i oznacza długość pliku o numerze i (1 ≤ s_i ≤ 10 000).

Twój program powinien wypisać n wierszy. Wiersz pierwszy powinien zawierać dokładnie jedną liczbę równą minimalnemu czasowi potrzebnemu do scalenia wszystkich plików w jeden. Każdy z następnych wierszy odpowiada łączeniu dwóch plików. Wiersz o numerze i + 1 (1 ≤ i ≤ n - 1), powinien zawierać dwie liczby całkowite k_i, l_i oddzielone pojedynczym odstępem, 1 ≤ k_i < l_i ≤ n. Liczby te mówią, że w i-tym kroku Bajtazar scala dwa pliki o numerach k_i oraz l_i. Nowo powstały plik otrzymuje numer k_i, a jego długość jest równa sumie długości plików k_i oraz l_i.

Jeśli istnieje wiele optymalnych kolejności łączenia plików, Twój program powinien wypisać tylko jedną z nich.