lsort

Se consideră o listă simplu înlănţuită (L1) ce conţine numerele întregi de la 1 la N (într-o ordine oarecare). Se doreşte construirea unei alte liste simplu înlănţuite (L2) care să conţină numerele din lista L1 în ordine crescătoare. Pentru a obţine lista L2, se vor şterge elemente din L1 şi se vor adăuga în L2, conform procedeului descris în continuare: iniţial lista L2 e vidă. La primul pas putem şterge orice element din L1 şi acesta se adaugă în L2. Apoi, în următorii N – 1 paşi, se poate şterge orice element din L1, dar acesta poate fi adăugat numai la începutul sau la sfârşitul lui L2. La final, L1 nu va conţine nici un element, iar L2 trebuie să conţină numerele de la 1 la N în ordine crescătoare. Întrucât există mai multe posibilităţi de a construi L2, vom defini în continuare costul construcţiei lui L2 şi vom dori să determinăm o posibilitate de construcţie a lui L2 care are costul minim.

Algoritmul de construcţie al lui L2 constă din N paşi, la fiecare pas ştergându-se un element din L1 şi adăugând acest element în L2 (conform restricţiilor precizate). La pasul i (1 <= i <= N), lista L1 conţine N–i+1 elemente şi lista L2 conţine i – 1 elemente. Dacă se mută elementul de pe poziţia k din L1 în L2 la pasul i (1 <= k <= N–i+1), costul acestei mutări este egal cu k * i. După mutarea elementului, lista L1 va avea cu un element mai puţin (toate elementele de pe poziţii mai mari decât k vor ajunge cu o poziţie mai în faţă) şi lista L2 va avea cu un element mai mult. Costul total al construcţiei lui L2 este egal cu suma costurilor mutărilor efectuate la fiecare dintre cei N paşi.

Date de intrare

Pe prima linie a fişierului lsort.in se află numărul N, reprezentând numărul de elemente din L1. Următoarea linie conţine numerele întregi de la 1 la N, separate prin cel puţin un spaţiu, în ordinea în care se află acestea poziţionate în lista L1 (primul număr se afla pe poziţia 1 în L1, al doilea număr pe poziţia 2 ş.a.m.d.).

Date de ieşire

Pe prima linie a fişierului de ieşire lsort.out se va afişa costul minim de construcţie a lui L2. Pe următoarea linie se va afişa modul de construcţie al acesteia. Pe această linie se va afişa ordinea în care sunt mutate elementele din lista L1 în lista L2. Primul număr afişat va reprezenta numărul mutat din L1 în L2 la primul pas; al doilea număr va reprezenta numărul mutat la pasul 2 ş.a.m.d. Numerele afişate trebuie separate prin cel puţin un spaţiu. În cazul în care există mai multe posibilităţi de construcţie a listei L2 având costul minim, se poate afişa oricare dintre ele.

Restricţii şi precizări

• 1 <= N <= 1000

Exemplu

lsort.in

4
4 1 3 2

lsort.out

15
3 4 2 1

lsort.in

7
6 3 5 4 1 7 2

lsort.out

43
6 5 4 3 2 1 7

Explicaţii

Pentru exemplul 1:

• La pasul 1, L1 = [4, 1, 3, 2] şi L2 = []. Se şterge din L1 elementul 3 (care se află pe poziţia 3) şi se introduce în L2. Costul acestei mutări este 3 * 1 = 3.
• La pasul 2, L1 = [4, 1, 2] şi L2 = [3]. Se şterge din L1 elementul 4 (care se află pe poziţia 1) şi se introduce în L2 (este evident că acest element trebuie adăugat la sfârşitul listei L2 şi nu la începutul ei; în caz contrar, lista L2 nu ar mai fi sortată). Costul acestei mutări este 1 * 2 = 2.
• La pasul 3, L1 = [1, 2] şi L2 = [3, 4]. Se şterge din L1 elementul 2 (care se află pe poziţia 2) şi se introduce în L2 (din nou, poziţia unde trebuie adăugat elementul este evidentă : la începutul listei L2). Costul acestei mutări este 2 * 3 = 6.
• La pasul 4, L1 = [1] şi L2 = [2, 3, 4]. Se şterge din L1 elementul 1 (care se află pe poziţia 1) şi se introduce în L2. Costul acestei mutări este 1 * 4 = 4.
• Costul total al construcţiei listei L2 este 3 + 2 + 6 + 4 = 15.